I have a GS3; Play worked on 4G network, but no updates or new apps on home wi-fi. I spent 3 hours trying all the cache clearings, restarts, and other advise listed here and on other boards. I even messes with the modem DNS and reset the wi-fi router. Nothing.
My fix was so simple I could shoot myself for wasting so much time on the rest. It IS a ROUTER issue; but an easy one!!! And you don't do anything to the router to fix it. (?) All you do is "forget" your wi-fi on yoru device and then re-aquire it like a new network. (you'll need your password for your wi-fi if you set one up.)
That easy folks!! Don't know why it works; it just does.