Hello @Miroslav Tsvetanov
I'm glad that you were able to resolve your issue and thank you for posting your solution so that others experiencing the same thing can easily reference this! Since the Microsoft Q&A community has a policy that "The question author cannot accept their own answer. They can only accept answers by others ", I'll repost your solution in case you'd like to "Accept " the answer.
Issue: Unable to upload photo for Entra users (not B2C) - Failed to upload user profile photo for Miroslav Tsvetanov.
Solution: Entra didn't had Office 365 Exchange subscription (which is not included in the personal Microsoft 365 plan).
After activating a license for Office 365 Exchange I was able to upload profile photos for users.
If you have any other questions or are still running into more issues, please let me know. We are happy to assist you further. Thank you again for your time and patience throughout this issue.