The criticism of Deus ex Machina is that it is un-earned. It represents literal divine intervention.
Other modern criticisms show a similar innate criticism when a protagonist has it too easy. Plot armor, protagonist-centered morality, chosen one, and Mary Sue are all criticisms against a character getting un-justified story 'gifts' from the author.
Imagine going to a sports game and the referees openly cheat for the team they like better. That team doesn't score legitimate points, but they win anyway. It's not necessarily a flaw in writing, but in our sense of entertainment, and 'fairness' in general.
It seems like a contradiction. Readers want magic in their fantasy, but they want the magic to have some limits, and they want it to be a challenge for the character.
They want the magic to be special, not routine.
Make it Harder
If the magic is treated as a skill that must be learned, we usually get a try-fail cycle, probably a mentor. The character attempts to use magic to solve their problems, but we see they are not skilled enough to take success for granted. We may see them fail at the exact magic task they later win.
Give it consequences
Another trope that prevents magic 'solutions' is to give it consequences. There is either a cost on the user directly, or a moral cost because of 'balance' or 'natural physics' or the law of conserved energy. The magician cannot make it rain here, without taking rain away from somewhere else. They cannot 'magic up' an easy solution without potentially creating a bigger problem somewhere else.
Add a twist
The magic may come from an unknown source, or it may be an illusion hiding a sinister agenda. The magic seems to be working fine, but actually some kind of debt is accruing. The magic may promise an easy solution, and through no fault of the protagonist it all goes pear-shaped. They didn't read the fine print, or the 'easy' solution was a lie all along.
Avoid 'just so' stories
A 'just so' story (named after the collection of bedtime stories by Rudyard Kipling) are elaborate justifications after-the-fact to explain how or why something evolved: How the Elephant Got His Trunk.
Readers are not impressed by a 'prophecy' that turns out to be word-for-word factual. It is clear the author wrote the story first and then made up a prophecy later to fit the circumstances of the plot and character.
Similar issues with an MC that had centuries of breeding to create a perfect hero, or a naïve MC who is too closely 'entwined' with the biggest evil arch-villain of all history. These characters are set up with special properties and circumstantial abilities, making them the only person in the galaxy who can win (the chosen one), but it is no coincidence. We know the author decided this and constructed aspects of the story to fit this premise.
Don't over do it
This can all feel like a contradiction.
Readers want magic in their fantasy, but they want it to be special. Magic should retain a sense of wonder. Use it sparingly and it can be exciting every time. You don't want to bring out a birthday cake for every desert. Build anticipation, and let the reader hope for it – all the better for story emotions if it's not a sure thing or has consequences – the reader can experience conflicted emotions of wanting the magic solution AND worrying what will go wrong.