AFAIK writable paper is not available in the Starwood, Docks or (as of late) the Exile's Camp. This makes acquiring it a bit tricky for characters that won't go into the ziggurat.
Would it be possible to make paper available from other merchants?
Blank scrolls work as writing paper, and quite a few merchants sell that.