Lollipop + Google Play - small application installs take 10 or more minutes?
Well I managed to solve it, got the idea from here: Application stuck in &quot;Installing...&quot; stage in Market. 

I went to Settings > Applications > Manage Applications.


Force stop the Google Play Store application
Uninstall updates for the Google Play Store application


It warned me that Google Play Store would be restored to its original state, I accepted.

After this, I launched Google Play Store and installing applications was lightning fast. :)