In a BTC-welcoming restaurant scenario, you are far more likely to receive your change as multiple BTC bills pre-printed by the restaurant in a small denomination conducive to leaving tips, with scratchoffs protecting the private key. Your restaurant receipt will list the firstbits of the change bills that were activated for you as proof that the bills were funded by the waiter before being brought to you.
Or they can make new private key for the change and print it on the receipt.
Or they can just send the change back to an address of your choosing - no need for physical bills at all. If you WANT that address to be a physical bill, however, you could certainly just provide the address for them to send it to.
There is no reason for a restaurant, pub, or any other modern establishment of the sort should be handing back physical Bitcoin change.