Disable Android Device Manager by going to Settings > Security > Device Administrators. Go to Apps now, disable Google Play Services, and then clear all its and the Play Store's data. Activate Google Play Services after rebooting the device.