Mark SharePoint Site as favorite - we couldn't add this to the sites you follow

We have a Microsoft 365 Tenant with E3 Licences, with all services enabled, so SharePoint and OneDrive for business.

One of our users reported, that he cannot mark a SharePoint Site as favorite. He gets the following error message:

"we couldn't add this to the sites you follow"

What I have checked:

• The user has OneDrive for Business
• The user has a correct licence assigned
• If the user opens the https://TENANT-my.sharepoint.com/personal/USERNAME/Social/FollowedContent.aspx site, he gets a permission denied error message

Does anybody know how to fix the issue?