I took me a few hours when the process should be really simple:
1. Purchase the basic service to get something like mystore@mydomain.com
2. Set your basic preferences here. Remember the google user that buy it is the administrator
3. Login with the new user created. User mystore@mydomain.com and yourpassowrd
4. Go to https://admin.google.com/ac/home that is the basic paid google console.
5. Select the security option and there in the Less Secure apps activate the option Allow users to manage their access to less secure apps. Save!
6. Now go to https://myaccount.google.com with the same new created user and from the left select Security
7. Select the option App password and there is the trick: Create a password for a custom app, and just click on Generate. This creates a long string that is going to be used only once on a computer. Dont close this window!
8. Go to prestashop email setting and use:
mail domain: yourdomain.com
smtp server: https://myaccount.google.com
Password: Use the generated string used on Step 7
Encryption: SSL and port 465.
Thats it!