Connecting to PayPal requires CURL for submitting transactions. And, it connects to PayPal on a SSL URL.

If you're doing a new install, there's a standalone CURL test script you can point your hosting company to so they can see the error themselves:
http://www.your_domain.com/extras/curltest.php?paypal=1
It uses the same CURL tests as the installer does.

They'll need to update their libcurl implementation, probably requiring a recompile of PHP and OpenSSL, with CURL options enabled. But, they're the experts in that area. If your interaction with first-level or second-level support doesn't get you in touch with someone knowledgeable, escalate to 3rd-level or to the department manager.
Or move to a host who knows what they're doing.