Hi there, I don't know if this will help others but I have been having this problem: each time I opened gmail or the SMS App, a random PlayStore ad for a game would pop up.
What worked for me:
1. Went to Settings --> Application manager
2. Located the (possible) offending app: Google Play Games...