I know of at least 3 LG phones owned by 2 other people besides myself with this problem. It started when Google pushed out Play Store 4.9.13 and short of contacting Google (good luck with that) there is probably no solution until they decide to update it again. I have a LG Escape that does the same thing. The other phones I know of are Optimus G's. I've done everything suggested, clearing data, cache, etc., I uninstalled Play and sideloaded it again, I even rolled my phone back to factory settings where Play Store worked until it updated within 5 minutes. About the best you can do is make sure you're not connected to wifi or data, open Play Store where it gives you the can't connect try again thing, click the menu then select settings and have it automatically check for updates. Or you can daily uninstall Google Play updates and immediately check for updates before it updates itself.
I actually thought about contacting Google via chat, but the last time I did that, my blood pressure shot up, I ground my teeth down, and I suddenly got the urge to choke someone.
Oh, BTW, I did contact LG, they didn't have a clue and said contact Google.