A paper bill is fine, but has one small problem. Unless you know exactly how much your purchase will be, there will be a balance left over on your paper bill. You can't just throw it away after an amount is swept off. You will need to move the balance to a secure address somehow. It would be great to have an automated way to make your bill expire after a predetermined set period of time and the balance is then moved to the next address in a series.
My initial thought was that the remainder will be sent by the seller to another address you provide (I even thought we might include it in the QR code), basically emulating how you pay with cash right now. I also assumed the buyer trusts the seller.
But your idea of expiration is much better, if it's doable. At a minimum, one could run another sweep after returning from the store ("gather all remainders from my used PaperCoins"), but doing it automatically would be cool.