Edit: This answer predates several rulings and clarifications made by WotC and Crawford in particular. I'm leaving it in place for historic purposes, but it's no longer a particularly useful answer.

Strictly speaking, there is no clear interpretation. All three cases are justifiable. Also note that 5e discourages literal "rules as written" meanings. As the designers have repeatedly said: "rulings, not rules." The rules were explicitly not written to be scrutinized as a lawyer scrutinizes the law, so we should not be surprised when the end result of "it's ambiguous" is what we find.

Firstly, "natural" melee weapons are, as far as I'm aware, considered melee weapon in 5e. [ See also.] There is no distinction between a mace and a hoof as far as "counts as a weapon" is concerned in 5e. I don't know if this is explicitly stated anywhere (I thought it was) but Unarmed Strike is explicitly listed as a weapon on the weapons table, and it's strongly implied since all monster stat blocks say things like "Bite Melee weapon attack: [...]". As far as I can tell, if you make an attack with it, it's considered a "weapon" in 5e. Something is a weapon if it's used to make an attack, then, not because it's got a weapon tag on it.

You could argue a Case 1 by saying that find steed only modifies the target of the spell. The spell still refers to "you," so even though it effects your mount, that extension does nothing. In other words, you argue that for Range: Self spells, "you" in the spell description means exactly, "you, the spell caster," and never, "you, the spell's target." This interpretation, however, also modifies spells like divine favor, detect evil and good, crusader's mantle (that one's a bit of a pickle to decode with a mount), and every other Range: Self spell. I'd argue it's all or nothing here. Either they all work on the mount (in some way), or none of them do. It doesn't matter how you rule here, but you should be consistent. Given the number and range of Paladin spells that are Range: Self I question an interpretation this narrow as being the design intent, but it's certainly supportable. About the only thing that reinforces this interpretation is the fact that the Smite class ability does not work on a find steed mount, but that's only because the class ability isn't a spell so it doesn't qualify for find steed's expansion.

The difference between Case 2 and Case 3 is deciding if find steed changes the wording of spells to "The first time both you and your mount hit with a melee weapon attack [...]" or changes to "The first time either you or your mount hit with a melee weapon attack [...]". Honestly, there's not enough information to decide either way. The spells are not written with find steed in mind, and find steed is not worded to make the end result clear.

You can argue Case 2 by saying, "The spell is intended to only affect a single melee attack; if it were intended to affect multiple targets, it would be higher level or otherwise deal less damage."

You can argue Case 3 by saying, "Find steed, like find familiar or hunter's mark, is a class ability masquerading as a 2nd level spell, and that wording was put there to have an intended effect. Furthermore, making a Paladin more deadly while mounted -- a fairly rare situation in most campaigns, IMX, and small Paladins are already less threatening -- is in-line with the desired result of the theme and flavor of the class. Given also the relative scarcity of spell slots, the additional power is probably not significant in most cases." This is not a particularly crunchy argument, but given that 5e does not separate crunch and fluff, it is legitimate.

If I were to rule conservatively, I would probably rule Case 2. If I were in a more liberal frame of mind, Case 3 would be reasonable. As it stands, I don't see any compelling justification for any one interpretation.

Resource Management during the Adventuring Day

As a class, the Paladin isn't overpowered. The Paladin does have a nice mix of weapon and spell skills to offer any party.

Discussion

On page 84 of the DMG the adventuring day around which the game is balanced calls for 6-8 encounters of medium to hard difficulty, and 2 short rests. If your DM isn't running that much challenge, then the Paladin's resource management problem isn't being put to the test as the game balance intended it to.

A Paladin can do large bursts of damage, for sure. What he can't do is burst damage all day, every round, for that many encounters.

Melee Attacks Available

You mention that the Paladin is now 5th level. This is a threshold in melee damage increase thanks to having gained the second attack per melee round. The initial increase in apparent power should level off a bit as you increase levels and the DM increases the CR of the monsters you face.

He has almost died at times

If he's playing "high risk - high reward" style, over time the odds will catch up with him. It appears that the shield spell that goes with his armor is giving more chances to not get hit. He is thus able to play a higher risk combat style than he might otherwise. If it allows him to do two handed weapon attacks, and still benefit from a shield through magic, that's more powerful than a paladin who has to use a shield and a one handed weapon to handle the rigors of melee combat.

That combined with the great weapon master feat might be what's causing this perception of great power. It might also be the pace of your adventuring day.

Spells Available

Per Long Rest, at 5th level, he has 4 spell slots of 1st level spells and 2 of second.

If he doesn't have to concern himself with casting any other spells (this has to do with your party make up and who the other spell casters are) then the paladin can use divine smite six times per long rest. That's a nice pile of bursty damage during some fights.

Is that "overpowered?" If you only have a few encounters per day, it can look that way. This is an adventure design challenge for the DM to address, as you both suspect.

Encounter design is explained on pages 81 - 85 of the DMG. The proposed XP budget for encounters and the adventuring day is built around a party of 4 characters, and the challenge ratings that accompany that XP budget. (For a party of 5th level adventurers, that's 3500 XP per character per adventuring day, 14,000 XP worth of monsters). If the DM reviews that and compares it to the challenge he's been offering you, he may choose to ramp up the difficulty.

A character can only have one long rest in a 24 hour period [PHB, p186]. This serves to limit the power of abilities and spells.

FWIW: in our party, the Paladin is often either the hero or the goat. He who lives by the burst, dies by the burst. He has a +1 magic axe (just found, has not used in battle yet) and some +1 bit of dwarf light plate. He does not overpower the rest of the party but he can hold his own.

In a tweet Jeremy Crawford (lead rules designer) advised:

Q: Is divine smite supposed to be limited to once per turn? Can I use it three times with extra attack and DW?
A: The limit on Divine Smite is the number of spell slots you have available to spend on it.