Buenas!
Desde el administrador de apps intenta borrar datos y cache de la play store.
(No borrar la play store)!
A veces solo con eso la play deja de dar fallos.
Si el fallo es por falta de espacio, desde ajustes/almacenamiento borra la cache.
Si usas la aplicación de chainfire, verás dentro de su menú la opción de desroteo completo.
Saludos.