Try going to Settings>Apps and look for Google Play Store and Google Play Services. Find them and clear the cache on both. Then reboot. If that doesn't work try holding down the power button and both volume buttons to enter recovery mode and clear the entire cache from there. That should do it. Occasionally I get an issue saying invalid APK when the cache gets too full, once or twice it just kept running in a loop.