This might me a dumb detail but make sure the date of the device is updated, like hour day or year. I am 98% sure I got this in the past and that was the way to get rid of it.
Sorry it did not work, and yes, I would be puzzled to but for some reason it is a problem nowadays, my smart TV can stop working because of it sometimes
Try clicking OK to see if the popup disappears. If it does, wait for a moment. If it reappears, return to the home screen, clear the background, and restart the game
Be sure to check that all Google services are up to date
If that doesn’t work, I’ve tried something else. Try launching the game from Google Play and make sure Google Play is running in the background while the game is running
Using a VPN has often worked for me (although almost the entire community is against it). Switching between the East Coast, the West Coast and the middle region always gives me a chance to get into the game