I had this error for weeks on my Galaxy S8! I tried everything I could think of, spoke with Sprint and Samsung- no dice. This is what we tried- apparently a number of different things can cause this error.
1. Clear Google Play Cache and Data
2. Force Stop app
3. Check to make sure date and time of phone are accurate- manually set or reset to auto
4. Remove and Re-add Gmail account
5. Switching to Airplane mode for a few minutes
6. Switching to WiFi/ Data
7. Delete any Proxy/VPN settings under WiFi
8. Running updates on all possible apps (this would actually work through Play Store for some reason)
9. Finally, the dreaded back up and factory reset
After the reset, I was still encountering the same issue which meant that whatever was causing it, was also being backed up. I played around for awhile and found that it didn't like my school gmail (corporation address). I tried a couple different ones until I found one that worked. Luckily, all I had to do was add extra gmail addresses instead of deleting my school on which I rely on heavily. For Google Play to connect to server, I just have to choose a gmail address (while in the app) that allows it do so.