Paper was only one written medium. All of the cultures you've listed constructed stone stelae with writing, like the Rosetta stone. South Asian cultures used palm leaves instead of paper. Maya used fig bark. Europeans and Nahuatl often used animal hides instead of paper. There's a long list.
Ok. Maybe I should have been more generic. Organic thin sheet material... velum, parchment, papyrus. The bulk of writing is done on material that is gone in a few thousand years at most.
Which still leaves stelae as already mentioned. There's also petroglyphs, ceramics, and paints. The point I'm trying to convey is that writing has never been limited solely to paper or even organic materials.