@Tobias Pahling Thank you for reaching out to us, to troubleshoot this issue we need authenticator logs/incident id - https://learn.microsoft.com/en-us/troubleshoot/azure/entra/entra-id/ad-dmn-services/send-microsoft-authenticator-logs.
However these logs can be analyzed with the help of our support team.
Before you reach to our support team, request you to check if there is any VPN software installed on your phone, if yes please uninstall it and try to add the account and check if it helps?