I'm not finding much in my Google searches other than clearing the data, cache, and uninstalling the updates.
Settings > Apps > Swipe to the left till you see All up top. Swipe up and locate Google Play Store. Tap on it. Tap Force Stop, tap Clear Data, tap Clear Cache. Reboot the phone.
If that doesn't work and since you've already uninstalled all of it's updates, your only solution might be to factory reset from the settings menu (as long as you're not rooted). Factory resetting will wipe everything except what's on the internal SD.