Actually, after thinking about this proposal for awhile I don't think the inevitable sentience of the paper is magical
We can do this by approaching the problem from reverse; if we assume that the paper is not intelligent, than there is no reason to believe that anything is intelligent at all. This is because a human body (and the intelligence we presume exists behind it) is merely a record of an acting intelligence, just as the paper is a record of acting intelligences. The fact that the body keeps a record via neurons rather than by graphite is merely a technical detail.
This curious fact, that recording an intelligence creates an intelligence, sounds strikingly similar to something Douglas R. Hofstadter said in Godel, Escher, Bach. When he stated that the mind is capable of sustaining self-subsystems that do not belong to the host body, he was, in effect, alluding to this very property. In his book, Hofstadter describes how when we come to know someone well we can often "project" them into our thoughts, he conjectured this was because we had assembled so many symbols relevent to them that they have become an actual intelligence existing within our minds. In effect, by recording and observing an intelligence, the record the mind creates becomes aware.
Ah, cognitive metaphysics at 6 AM...