Sorry but I didn't write down everything I did. But I found two places on the phone (Samsung Android 4.3) where I had to enable this background data option for Google - not just one!!!
The second one was Settings / Data usage / then you scroll down to your Google Play Store app / click to open it/ scroll down again until you see the "Restrict background data" option at the bottom
Uncheck. Before this I had removed the google account, cleared cache, data, everything, restarted phone... what a nuisance
Then I tried the "Google Play store" again and put wi-fi on just for assurance. "Google Play store" finally asked me to sign in or whatever and downloaded the app.
Google Play store is the most stupid thing ever