Hi Alex,
I'm going to go with burn up and disintegrate.
On leaving the ISS the paper will be travelling at around 7.6 - 7.9km/s. It will have to drop from ~400km to ~120km before there's sufficient air to deform and really decelerate it. Assuming it gets into a suitable trajectory for re-entry (and I'll leave the orbital mechanics alone), during the decent, the rarefied air at the reentry interface will be struck with such energy as to ionise molecules and generate enormous heat even for a piece of paper. G forces will (probably) be significant (regardless of low mass/density, and depending on trajectory) and the paper will crumple and disintegrate (ultimately like being blasted with a blow torch).
The Register has a project (called
LOHAN) to release a "paper" plane from the edge of space using a helium balloon, but that's nowhere near the altitude of the ISS and not moving at anywhere like those speeds, so very much less energy will be dissipated.
Also see this:
Why Didn't Baumgartner Burn Up on Re-entry?