Guys, I had tried almost every step suggested by Google and other forums but nothing worked. Finally, tried this as this fixed this issue for me today:
Settings > Other accounts > Google > More > Remove account
Now, open Play Store and sign in with another working Google account. Try to download & install an app (preferably smaller size) or update an existing app. After this, again remove this Google account by navigating through the steps mentioned above. Post this, open Play Store and now sign in with your original Google account (through which you faced this issue).
You should no longer see this error.
