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.
Counterparty risk is a necessary evil when sending fiat. An ATM that dispenses fiat is subject to compliance laws to mitigate risk. Please don't conflate fiat with a Bitcoin transaction. Of course there are very secure ways to send bitcoins, but this is about sending fiat using bitcoins as a payment system only.