Play store doesn't work

A

AC Question

Play store is supposed to do one thing. To download apps into your phone. And it doesn't.
Whenever I try to download smt, the bar keeps going endleslly, and it says downloading, but nothing happens, like actually downloading the damn thing, or showing percentage progress, nothing. If I pull down the notification bar, it says downloading is paused. Awesome. Things I tried so far and that everybody would other wise suggest I do: Deleted cache and data for Play Store, deleted cache and data for Play services, Deleted cache for Download manager, cleared data and cache for Google Services framework, force stop play store, force stop download manager, rebooting device several times during process, deleting Google account, making new account, Factory reset, reset app preferences (which does nothing btw, I don't even know why it's there), etc.
So the quiestion is: Is it just me or Android started sucking big hairy balls since Lolipop 5.0?