The "App credentials authentication failure" appears when the stored credentials no longer enable the application to sync users:
Here are a few different solutions to this problem.
1. The Azure AD client secret has expired. Follow this guide to create a new secret.
2. The Azure App registration does not have permission to the Microsoft Graph API. Access to this API is required after June 2022. Follow this guide to add the additional permissions.