The Police is the best bet? Come on guys, be more confident with yourselves. I'm sure I'd make a better try than the Police would on finding the owner. I wouldn't even trust handing over a private key in the police department.
I knew that answer would probably be controversial. The thing is, even moving the private key can be a problem because when there's no way of proving or finding who owns it. The person might come back to that spot, and try to find it. So, the very act of moving it or taking it could be morally wrong.
That's the one reason why I even considered myself that police would be an option. Because if people look for stuff where they lost it, and it is gone, they often proceed by asking the police or the local lost & found office. But the drawbacks (trustworthiness of police officers or any human, for that manner, not to take the coins) do outweigh the advantages in my opinion.
However, then you have the issue of not moving it, and potentially allowing the next person to come along, and steal it. Giving it to the police, you assume they'll have some sort of moral decency, and influence, but probably not. I mean, they probably wouldn't know what to do with it, and you've already moved the private key at that point.
There might be one alternative: take it and leave behind a note with your phone number or email address so the original owner can contact you to pick it up, when they go looking for it. If this note has the same shape, size and material of the found paper wallet, you don't really change the 'situation' at all. It has the same chance of being destroyed, blown into the sea, stolen, trashed as the original paper wallet.