There is no recipe for paper in NEI, and using sugarcane in the vanilla patter doesn't work either.

There are recipes for it later on. Did you have an immediate need for paper for some reason?

I can't check right now (server is unavailable) but if I recall correctly it was a quest that wanted me to make a book of some kind, and that required me to have paper in order to make the book. Which is why I expected to be able to make said paper at that point.

That quest will be accessible once you learn how to make paper. :)

... er well that quest is accessible now. :P