No matter what the security features of the paper wallet, the fact will remain that the ATM owner will always know the private key associated with the paper wallet...
Not necessarily. The paper wallet code could generate the key in memory and delete it after being printed. That code could be open sourced to demonstrate that detail to all who wish to verify.
I don't think it would be possible to verify that a specific ATM is using a specific code. Nor would it be possible to verify that the private key is truly deleted from the ATM's memory.
As mentioned above this is very similar to creating a private key on the "server" side and is very risky and should not be used