Si Play Store viene instalada de serie, entonces difícilmente vamos a poder desinstalar esta aplicación. En esos casos no quedará otro remedio que rootear el teléfono para poder instalar una aplicación que permita desinstalar Play Store o instalar una Custom ROM a través de un Custom Recovery tipo TWRP.
Lo que sí que vamos a poder hacer en todos los casos es desinstalar las actualizaciones. Para ello entramos en Ajustes > Aplicaciones instaladas > Google Play Store y ahí seleccionamos Desinstalar actualizaciones.