Eh, the texture looks more like a stucco texture than paper (or maybe its a wrinkled up paper texture)
what may help make it look more like paper is rather than just adding the effect over the whole image, instead find a good image of paper, a scan of paper, where instead of looking wrinkled, it looks flat, but you can see all the fibers and imperfections. Take that scan of paper, and layer it on top with an image editor, and set the blend mode to multiple, then probably sett the effect to 50% opacity, that way everything looks like its printed on paper rather than a paper effect in the back ground. additionally, I assume that every image will have this effect baked in, so what I would do in a preview image like those above is work with one image at a time, use a slightly different paper texture (or offset the location) so that each character looks to be printed on a different piece of paper (it will help make the effect not look like its just layered over the whole screen), On top of that, I may even make a white edge or something to make it look like the characters are cut out of paper (if you want that effect).
one issue I've had in the past is sometimes I want whites to looked like they are inked on, rather than just looking like paper showing up through the layers of ink. So I've played with different blend modes (such as 'overlay') or I'll get real fancy and use the values of the source image to control what blend modes are used on what part of the image (but I do this using the 3D modeling program Blender, not image editors like Gimp).
As for your concern about dull colors, it looks fine. I even think the grass and bricks look better. maybe a bit annoying on the flat color of the billboard, and I would say that it really messes up the glass, and maybe obscures the characters a bit. So maybe finding ways of applying the effect at different %'s for different parts of the image would help alleviate your concerns.
