I would rather keep both classes around and just reduce the availability of magic being able to do ANYTHING without reason or cause.
I doubt many fans would accept reigning in magic to the degree that it would be balanced with something like the 5e playtest fighter or early-D&D fighter or even 3.x fighter. 4e only brought the wizard down a notch or so and that brought howls of derision.
I suppose part of the appeal of D&D has always been a bit of 'power fantasy,' getting to do the impossible.
Maybe, ideally, the game could have modules to cover very different styles.
One might have rules for very simple fighters and wizards and everyone in-between who balance at a 'gritty' power-level, with fighters doing mostly-realistic things and wizards doing mostly rituals and 'magic' that might conceivably be little more than legerdemain, chemistry (and/or other anachronistic knowledge), and cunning.
Other modules might add more extreme fantasy elements, making wizards into true casters using undeniably-real magic, even in combat (with some difficulty), and fighters into super-human paragons of strength and courage who, likewise, do impossible things.
The dial could go up so far as to have virtually super-hero-like characters of any class.
Okay, first I would speculate that either the Irish king has some form of magic, god-blood in his veins or simply DIDN'T do what he is known to have done. If he is just a "fighter" then there is no earthly explanation of how he could have done what he did without magic.
There's no realistic or scientific or reasonable-to-a-modern person reason why a 'normal' person could punch the top off a mountain in rage. In legend, and in fantasy, just being a king for instance, makes you no longer an ordinary person, and extraordinary people, in an extremity of emotion, doing something impossible isn't out of place at all.
I think this comes from the conflating of fantasy & science-fiction in recent decades. In sci-fi, the writer asks the reader to accept some outlandish assumption (like aliens or time travel or some improbable technological advance) and then explore with him the ramifications of that outlandish idea in an otherwise normal, scientifically plausible world. The fantasy genre can be looked at as a science-fiction setting in which the outlandish assumption is "there is magic." So, you hold anything that's "not magic" to realistic standards. That's not fantasy. In fantasy, the whole thing is outlandish. There is magic, faeries, dragons, unicorns, demi-gods, there is true love conquering all, bards singing the dead back to life, lands falling to famine because their king is depressed, and impossibly brave heroes doing impossible things. There isn't one 'assumption' to be explored in a scientifically-consistent world, there's a whole world that's fantastic.
So the solution you propose is to remove anyone who can't wield magic... because ... people who can wield magic are overpowered?
My solution would be to present a balanced game. If the balanced fighter is so unacceptable to such a broad swath of the fanbase that only underpowered fighters can be used (which, you, for instance, absolutely insist upon), then they shouldn't be used as a PC class.
Mine would be to remove (or decrease) those who are overpowered, *shrug* that is just my preference I guess. I would prefer to eliminate things that would break my game instead of making EVERYONE in my game have powers that can break the game.
I don't see that happening, but see above about modular power levels. It might be possible to present the game with some sort of 'dial' or series of modules in which the amount of power/un-reality in the game can be adjusted. At the low end, fighters are just guys with swords able to do only what real life guys with swords can do, and wizards are just alchemists and sages, able to do only what real life alchemists and sages could do, and at the high end, they're both super-heroes, with several notches in between.