I've made a quick mockup in GIMP of a couple of paper samples. Would this kinds of thing be to your quality standards? (artefacts on the image such as corner stains and rust marks really help make it pop, but I'm starting simple first).
If this is indeed the kind of thing you'd find acceptable, I could look into writing up a Script-Fu automated process. I haven't written Script-Fu before, but I might be able to eventually get something working.
My trick is using perlin noise on a transparent layers and with layers shifted with translucent pixels, shifting the hue and opacity of each layer.
Above uses Perlin noise from the website: http://kitfox.com/projects/perlinNoiseMaker/
The above uses Perlin noise generated natively in GIMP