Cómo reinstalar los servicios de Google Play

Como preguntó Firelord, ¿desinstalaste las aplicaciones o sólo las actualizaciones?

Si solo las actualizaciones, si abres el play store en tu teléfono, y debería buscar actualizaciones tanto en tu play store como en play services. Si no sucede automáticamente, trate de borrar los datos de la aplicación de la tienda de juego, y luego tratar de encontrar manualmente la actualización por ir a la actividad de configuración de la tienda de juego y tocando en el número de versión.

Si has desinstalado las aplicaciones, supongo que ya tienes acceso Root, porque desinstalarlas sin acceso Root es muy difícil. En este caso, flashea un recovery a tu teléfono si no lo has hecho ya, y flashea el zip de aplicaciones de Google (GApps) que coincida con tu versión de Android, y borra la caché y el caché dalvik si es necesario a través del recovery después de la instalación.