If OP can properly set up a cold storage (maybe with Tails?) it would be much better to move the coins to a new address, so the owner has a better chance to notice something is wrong.
Disagree. By far the most likely way that these coins will be recovered is simply by the owner realizing their paper wallet is missing and accessing a different back up to move the coins. If you move them to a new address, then you completely prevent this from happening.
If you want to move the coins so the owner notices something is wrong, then sending them back to the same address is the best option. Add in an OP_RETURN output as mentioned above if you feel life it.
If easternklaas is unsure about how to do that, then he can simply share the address here and someone else can create the necessary transaction (send all coins back to the same address and add an OP_RETURN output which directs to this thread) which would just require him to sign and broadcast.