Processes in Microsoft 365 for setting up Office apps, redeeming product keys, and activating licenses.
Solution
The solution described at https://docs.microsoft.com/en-us/office365/troubleshoot/authentication/automatic-authentication-fails#resolution eventually worked for me.
TL;DR
Run the following command in PowerShell:
if (-not (Get-AppxPackage Microsoft.Windows.CloudExperienceHost)) { Add-AppxPackage -Register "$env:windir\SystemApps\Microsoft.Windows.CloudExperienceHost_cw5n1h2txyewy\Appxmanifest.xml" -DisableDevelopmentMode -ForceApplicationShutdown } Get-AppxPackage Microsoft.Windows.CloudExperienceHost
During my research I also came across https://docs.microsoft.com/en-us/office/troubleshoot/activation/reset-office-365-proplus-activation-state, which might be helpful for some people, too, but didn't work for me, unfortunately.