When you say you already checked Internet connectivity, do you mean that you specifically tested connectivity to Check Point services? or just the Internet in general? If just the Internet in general, have you seen or tested this sk article? If you run some curl_cli tests, do you see them passing all the way through? I have an environment with multiple layers of Firewalls between it and in the Internet and had to write explicit rules in those other Firewalls to accommodate the implicit rules allowed in others.
This also may seem like a strange question, but do you use Geo-location enforcement? If you do, I've seen issues post R80.10 where the Gateways try to reach "c12resolver.ctmail.com". It appears that Check Point's Geo-IP Database places this IP in Hong Kong; which we block. I had to put Geo exceptions in for 103.5.198.210 and 84.39.153.31. The function of those IP's is explained in this sk, but not under the context of the connections failing.
Since it says this is intended for URL Filtering, it may not be related to your issue at all. But I suppose couldn't hurt to check whether connections to this IP's are being blocked.
R80 CCSA / CCSE