I would take the piece of paper, but I would not take or move the coins. I know that my intentions aren't bad and I am OK taking it. I can't say the same thing about the next person that walks down the same path on the beach I did. I would then do all I can to find the wallet's owner, but even if I failed I wouldn't move the coins or consider them to be mine. I wouldn't give the paper wallet to the police. I have seen their competence when a friend of mine had his wallet stolen. Someone found it empty of all money and returned it to the nearest police station. The rest of their procedure is a joke I am not going to get into right now.
It's why I gave a few possibilities, by removing that piece of paper or whatever the deemed backup is, you could potentially be making it impossible for the original user to recover it. However, as you rightly said, that wallet could've come from miles away since the tides could be covering it. I'm kind of glad that this discussion came up, since the beach provides certain moral decisions, which aren't easy to make, as there seems to be a scope of consequences whatever you might decide to do, hence why I compared it to the train tracks, where doing nothing also presents a problem.