I have verified that the server ONLY uses TLS 1.2 as an allowed protocol. 1.0 and 1.1 have been disabled. We are also using .NET framework 4.6 and Kentico version 9. See output from IIS Crypto, which matches settings in RegEdit.
I can also browse on that machine to https://tlstest.paypal.com/ and I get the "PayPal_Connection_OK" message.
All pieces should be in place. Not sure what else could be missing.