Я не пользуюсь Google Play, но у меня тоже изредка возникает такая проблема.

Ребут всегда помогает, но есть парочка обходных решений

1. Ставить приложения через adb

Заходим в настройки разработчика, включаем отладку + отладку по сети. Можем подключаться к телефону через комп (по USB), а можем ставить локальные apk-шки прямо из Termux.

adb connect localhost
adb install /path/to/file.apk

2. Либо можно не париться и сделать проще.
Заходим в консольку на телефоне (Termux подойдёт также)

pm install /path/to/file.apk

Замечание: если мы обновляем уже установленное приложение, то тулзы запускать с ключом -r, иначе они будут ругаться.
Например, pm install -r или adb install -r