[Marshland]

FWIW, I've just updated to Kitkat and experienced this problem, trying both fresh installs from the Playstore and backups from Titanium. After a search, I found this resolved the issue:

Go to: Settings > apps > all > Google Services Framework > clear data.
Then clear data/cache for the Play Store.

Reboot, and go to the Play Store, you'll then need to give the usual permissions again.