You probably need to set up SPF, DKIM, and DMARC. Gmail won't accept email without them.
Since you are using Cloudflare, you'll need to set these up yourself. For SPF, you can create a TXT record with a blank name (i.e. the same name as the domain) and this value:
"v=spf1 a mx include:johnny.heliohost.org ~all"
For DKIM, you need to enable it in Plesk under Mail Settings, apply it, then create the DNS records shown under the "How to configure DNS" link next to the option (usually two records).
For DMARC, you can create a TXT record called _dmarc and use this value:
"v=DMARC1; p=quarantine;"