I'm on N4, running Android 4.3. I tried clearing data from Download Manager, Play Store, and Google Services Framework, and rebooting, but it never worked. The only thing that worked was this:
"Simply remove the Google account, reboot, and then re-enter your Google account. Takes a couple of minutes, but fixes the issue instantly."
I found that at Droid-Life. Good luck!