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.