Device does not register with Google to access the Play Store
I finally made it to work, I'll be posting what worked for me so it hopefully helps someone facing the same problem. 


I manually downloaded the latest (version 6 as of now) of the PlayStore app on my PC and installed it on my device
Then I went to the apps configuration and cleared cache data on all Play services I could find.
Then rebooted my phone and that was it