Google Apps not responding even after factory reset
In case others have the same problem, I was able to solve mine by reinstalling the Android OS and giving Google access to all permission options which it asks for (e.g. using your location, collecting customary information about you, etc). In principle, the installation process gives you the right to forbid the mentioned options, however, when I did that the first time, the problem remained.

Frankly speaking, I would have liked if Google did not follow every movement of mine (like Big Brother in 1984), but at least now I can use my phone normally. It seems we should reconcile with the fact the our tech tools have permanently occupied our private lives.