Thanks marbillphone for the hint.
I even found an easier way.
1. Clear cache and data of the Photos app (settings - apps)
2. Clear cache of the Google Play Service and further click on "Manage space" and there "clear all data" (settings - apps)
3. Run Google Photos, select your account and...