My Samsung Galaxy S4 is "Rooted" long time ago..
But same like your problems a few days ago can't connect to Google Play Store..
What I'm trying is :
1. Clear Data the "Google Play Store" - Not Work
2. Disable "Google Play Store" and when asking for restore to original version "Yes" , It's working for a while but when Google Play Store Automatic Update Itself , this problems happened again.
3. Download Latest Firmware from "SamMobile" for my Phone and my Regional , Using Odin to Restore
4. Using KingoRoot to Root Again my Phone.
Until today after do step 3, Seems everything works fine...maybe you can also try that..hope it helps..