The entire concept of marking coins with trustworthy seals was exactly to basically invent fiat currency as risk mitigation: coins bearing the seal would be honored, and from that it was a short hop to "what if I just presented an IOU with the seal of the local gold merchant?"
1. most physical paper has a relatively short life, so one would not expect it to last as long as metal tokens
2. paper was only available in much of the world several thousand years after the first currencies began, so it's not suprising that we have little record of paper money from very old civilizations.
3. the idea that there was no cheating by fudging numbers before paper currency is completely ahistorical. The nature and ease of the fudging may have changed, but the fudging itself existed long, long before paper currencies became common.