And that's the tricky part: even a signed message from the address that funded the wallet doesn't necessarily mean it's the owner (it could be the guy who sold the Bitcoins to the current owner).
If you buy or get a paper wallet from someone you can't 100% trust for the lifetime of the paper wallet, you should move the coins off the paper wallet and create your own one as destination if you want to keep a paper wallet.
I meant the previous owner of the Bitcoins, who can sign a message from the sending address. I didn't mean the previous owner of the paper wallet to sign it.
An OP_RETURN "Found lost or stolen paper wallet, see thread on bitcointalk.org" as transaction output at the proper place speaks for itself, but frankly isn't for newbies.
Although technically better, it doesn't make it more likely for the original owner to read it. Hence the "vanity burn address" suggestion.
@easternklaas, When I read your location, it occurred to me that a few months ago I read about floods in that part of
Australia, so I wonder if it is possible that some of the floods actually caused that paper wallet to appear on the beach?
This makes sense.