I did a brief search on the Internet what could be causing such behaviour and majority of posts were pointing at some issues with cached data by Google Play Store and/or Google Play Services somehow breaking installation process. They were suggesting cleaning cache of these to solve the problem.
