Here is a detail step by step that will hopefully keep you from doing a factory reset. There's a couple things to touch on before beginning. Placing your phone in airplane mode will ensure updates don't start until you finish the entire process. If you are rooted disable all applications that require root (Task & Scripting Apps, Firewalls, Adblockers, etc) Also anything of that nature for non-root, any 'run at boot' type App. Feed Readers, Podcast Apps, basically anything that wants to sync on reboots and/or connection changes.
1) Turn Off & Reset Networking
1. Turn ON airplane mode.
2. Open the Settings App.
3. Under the "Wireless & Networks" header tap More > Reset Network Settings.
(Samsung: Settings > Connections > More Connection Settings > Reset Network Settings.)
2) Remove Google Account
This will remove Information linked to your account until you re-add your account Make sure you backup important information before this step
1. Open the Settings App.
2. Under the "Personal" header tap Accounts. (No header on Samsung)
3. Tap Google > Select the account you're using with Google Play
4. Tap More > Remove Account.
3) Clear Cache & Data from Download Manager
1. Open the Settings App.
2. Under the "Device" header tap Apps. (No header on Samsung)
3. Scroll to and tap Download Manager.
4. Tap Force Stop.
5. Then tap Storage.
6. Tap Clear Cache.
7. Then tap Clear Data.
4) Clear Cache & Data from Google Play Services
1. Open the Settings App.
2. Under the "Device" header tap Apps. (No header on Samsung)
3. Scroll to and tap Google Play Services.
4. Tap Force Stop.
5. Then tap Storage.
6. Tap Clear Cache.
7. Then tap Clear Data.
8. (if available) Tap Uninstall to uninstall system updates.
5) Clear Cache & Data from Google Play Store
1. Open the Settings App.
2. Under the "Device" header tap Apps. (No header on Samsung)
3. Scroll to and tap Google Play Store.
4. Tap Force Stop.
5. Then tap Storage.
6. Tap Clear Cache.
7. Then tap Clear Data.
8. Tap Uninstall to uninstall system updates.
9. Repeat these step for all other existing Google apps. **Backup your data**
6) Things to check in the Setting App before rebooting
Use the Search in the Settings App, some of these may not be found in every Android version.
- Reset App Preferences in the Apps settings menu.
- Reset Permissions in Privacy Guard and set it to OFF.
- System Profiles are set to OFF.
- Developer Options are set to OFF.
- Under the "System" header tap Accessibility, Switch all to OFF.
7) Reboot, Connect & Sign-In
1. Power on / Reboot your Device.
2. Open Settings > Display > Screen Timeout. Set it to Never.
3. Plug your device into a power source.
4. Allow a couple minutes to pass then turn OFF airplane mode.
5. Turn Data off.
6. Open Google Play.
7. Choose your network.
8. Sign into your Google Account.
9. Tap the Home button.
10. Set your device down for 10-15 minutes and let Google process updates, sync, etc.
11. Reboot and access Google Play as you normally would.
All information can be found in the Play Store Help: extra steps to fix Google Play Issues