I've used paper, and (various types of) adhesive contact paper. None was pleasant to use: the edges rub against the skin, and the paper gets stretched (!) and filthy shockingly quickly.
Now I sand the surface down a bit and brush on a few light coats of varnish. I used masking tape to define the area the first time, but if I had to do it over again I'd just roughly blend at the edges. The result is a smooth and mouse-compatible surface which thus far has lasted better than the rest of the desktop (and which in any case can always be topped up). The varnish protects the desktop from further wear and adds microscopic texture which your mouse can process. I used marine varnish, which is formulated to withstand far more abuse than your mousing hand can inflict.
My mousing area still had plenty of visible texture so gloss varnish (which roughly matched the shininess of my desktop) worked fine, but if the area was smooth enough to confuse a laser mouse I'd use matt or satin varnish instead. (Though again, the 3D surface of the varnish will likely suffice.)
BTW, on the first coat I had no idea how to varnish things and ended up with significant brush marks which I had to sand down with fine sandpaper. Learn from my mistakes: only dip the very end of the brush, and do thin coats.