Thought of one fairly abusive, quite expensive way to do it. It basically comes down to finding a way to use Heighten Spell for free, so that you can get an effectively-6th-level spell that you can still cast from your 4th-level-or-lower slots, and then coming up with a way to spontaneously convert a spell you have into a spell of the same level from a domain. To do the first, there are three options: Divine Metamagic, Talfirian Song, or Earth Spell + Improved Sigil (krau); to do the latter, there are two options: a healing domain icon, or getting the Healing domain and choosing it for Domain Spontaneity.

In detail, you must:

• Gain the ability to raise a spell’s effective level to at least 2 higher than the spell slot it’s in. These are sorted first by effectiveness and then by ease.

  • Divine Metamagic, choosing Heighten Spell as the choice. This lets you raise the spell level of any spell to an arbitrarily high number, based on your uses of Turn Undead. This method will require a minimum of three Turn Undead uses per heal cast; more if you’re doing it with lower-level spells.

    • Note this requires that you have Heighten Spell first.

  • Talfirian Song from Races of Faerûn allows you to use daily bardic music uses to Heighten a chosen illusion spell for free. You can use as many uses as you like, to raise the spell up to 9th level, so this more than covers us. The example explicitly raises a bard spell to 8th level, so there is no concern that it was not intended to exceed the maximum level for a particular class.

    • Note this also requires Heighten Spell, and for you to be a Tethyrian human.

      • You may be able to qualify for this and Improved Sigil (krau), below, if you are an illumian from the appropriate area (or you’re not playing in the Forgotten Realms and the regional requirement is adapted), since Races of Destiny says that creatures with the (human) subtype qualify for racial feats that require the human race, and illumians have that.

    • This requires bardic music; a paladin can get that as part of the harmonious knight variant in the Champions of Valor Web Enhancement, which replaces Detect Evil with Inspire Courage +1, once per day. It doesn’t, by itself, give more uses than the first one, but From Smite to Song in the book itself can get you some, as can Extra Music in Complete Adventurer (four uses per feat).

      • This requires being specifically a paladin of Milil, at least in the Forgotten Realms. This turns out to be grossly inconvenient since you need the Healing domain, which Milil doesn’t offer, as well as some way of getting an illusion spell (and none of Milil’s domains offer that). Heretic of the Faith from Powers of Faerûn can swap one domain for one Milil doesn’t offer, so that covers Healing, but this likely won’t be good enough for a domain icon, so you’ll need to actually get the Healing domain from a prestige class.

        This is much easier if you are not in the Forgotten Realms, and can just adapt the harmonious knight to someone who offers, say, Healing and Magic.

      • Alternatively, you could just dip bard. There’s nothing saying the bardic music and the spells have to come from the same class.

    • Talfirian Song requires that you choose a spell from the Illusion school. This is the hard part: somehow, never in the entire history of 3.5 did Wizards print even a single illusion spell on the paladin spell list. You can get one the same way we’ll get heal itself, of course: domains. With thanks to imarvintpa’s Find Spell app and Curmudgeon’s domain list, here is what seems to be a complete set:

      • Celerity (Spell Compendium): blur (3rd)

      • City (Races of Destiny): winding alleys (3rd)

      • Creation (Spell Compendium): minor image (2nd)

      • Dream (Spell Compendium): phantasmal killer (4th)

      • Entropy (Fiendish Codex I: Hordes of the Abyss): vision of entropy (2nd)

      • Envy (Spell Compendium): disguise self (1st)

      • Gnome (Spell Compendium): silent image (1st) and more

      • Illusion (Spell Compendium): silent image (1st) and more

      • Lust (Spell Compendium): invisibility (2nd)

      • Magic: Nystul’s magic aura (1st)

      • Shadow (Eberron Campaign Setting): shadow conjuration (4th)

      • Spell (Spell Compendium): silence (2nd)

      • Trickery: disguise self (1st) and more

      • Wealth (Spell Compendium): obscure object (2nd)

      There is a trade-off between getting a low-level spell and a high-level spell: low-level spells are available earlier, and you get more of them, but high-level spells require fewer uses of bardic music to get them up to 6th level. Probably easier to get more uses of bardic music than it is to get more 4th-level spell slots though.

      Non-domain options for getting an illusion spell may exist, but I haven’t found them yet.

      • Special mention for harmonious knight paladins of Milil: Milil doesn’t offer any of these domains, and you had to already use Heretic of the Faith to get Healing since he doesn’t offer that either. You can still get the Magic domain, however, by becoming a seeker of the misty isle, a prestige class in Complete Divine. Some serious problems exist with this, however:

        • You have to be an elf or a half-elf, which conflicts with the human requirement for Talfirian Song. Races of Destiny suggests a variant in which half-elves count as human by default, so that may be an option; if it isn’t, Races of Destiny has a Human Heritage feat for you. Either way, Improved Sigil (krau) is out.

        • Seeker of the misty isle doesn’t grant the Magic domain until 7th level, ECL 12th, and it costs a level of spellcasting to get that far. Thus you’d be far better off just not worshiping Milil in the first place, and dipping bard.

        • The class doesn’t have any requirements on your faith, but it is heavily based in the history of the elven race and its pantheon; one of the class features is even named Corellon’s Perception (this is an extraordinary ability, however, not a divinely-granted one). This is kind of awkward for a half-elf who specifically favors his or her human heritage.

  • Earth Spell from Races of Stone allows you to get a free extra +1 in effective spell level when you use Heighten Spell. So if you prepare, say, heightened cure moderate wounds in a 4th-level spell slot, it counts as a 5th-level spell. This gets you halfway there.

    • Note this also requires Earth Sense and Heighten Spell.

  • Improved Sigil (krau) from Races of Destiny allows you to cast a chosen spell as if it had a free +1 spell level “as if by Heighten Spell.” So, for example, if you choose cure moderate wounds, it counts as a 4th-level spell even though you prepare it in a 3rd-level spell slot. More importantly, if you also have Earth Spell, your heightened cure moderate wounds counts as a 6th-level spell, even though you prepare it in a 4th-level spell slot. This is sufficient for heal.

    • Note this requires you to be an illumian.

• Get a way to spontaneously convert your spells to spells from the Healing domain through one of these two methods:

  1. Get a domain icon for the Healing domain. These items are found in Faiths of Eberron, and allow you to spontaneously convert your spells into spells from one of your deity’s domains, even if you don’t have that domain. Note that each icon only works three times per day; you’ll have to buy more if you want to use it more often than that.

  2. Gain the Healing domain, and then Domain Spontaneity from Complete Divine allows you to spontaneously convert a prepared divine spell to a spell of the same level or lower from a chosen domain that “you have access to.” Note this burns a use of Turn Undead each time you do it.

     Options for access include (with thanks to the Lists of Stuff):

     • Divine Disciple 1st,¹ ECL 6th,² Forgotten Realms Campaign Setting

     • Singer of Concordance 2nd, ECL 10th,² Races of the Dragon (must worship Io)

     • Contemplative 1st,¹ ECL 11th, Complete Divine

       1. ^{Requires that Healing be a domain offered by your faith; note that Heretic of the Faith from Power of Faerûn can solve that problem for exactly one domain.}

       2. ^{Provided you already have the spell-level improving feats above. In some cases, more than two spell levels are necessary to get in as early as listed, which means Earth Spell + Improved Sigil (krau) won’t cut it.}

  You can now spontaneously replace your effectively-6th-level spell with heal from the Healing domain. Note also that you do not need to worry about the usual limit of only preparing domain spells once per day (per Complete Divine), because you are not preparing heal, you are casting it spontaneously.

The Divine Metamagic route is the most straight-forward and least costly, since its only requirement is that you worship a deity who has the Healing domain, and it only takes two feats to accomplish. The Talfirian Song route would be pretty simple, if you didn’t have to worship Milil and there was even a single paladin illusion available, but the complications that Milil causes and the need to finagle an illusion onto your spell list kills it. The Earth Spell + Improved Sigil (krau) is extremely expensive in terms of feats (four), plus it locks your race, but it does have the advantage of being free to use thereafter (Divine Metamagic requires turn undead attempts and Talfirian Song requires bardic music uses).

It will make them stronger, but not much

This answer is about Wizards, but I agree that more spells from the same list are not much improvement. Usual Sorcerers take the 15 spells¹ they find best or strongest, so by definition the next 5 will be weaker.
They have the same number of slots, and more importantly, the same number of actions per encounter.

Example: Lightning Bolt

In most situations Fireball is better than Lightning Bolt, as it usually covers more area. It effects more enemies, so most Sorcerers only know the former as they can't afford both.
After this change they might be able to take both, but in the vast majority of the cases, they will still chose Fireball to cast. Only in the few times when the enemy is lined up nicely, or is resistant/immune to fire but not to lightning, will they cast Lightning Bolt. So in about 10% of encounters, they will not lose 50% of their damage (they will lose some damage, as most likely less enemies fit into a line than a sphere).

This comes up to 5%, hardly unbalancing².

Spells from other lists

This is where the idea can go wrong, so you have to examine it on a case-by-case basis:
A twinned Tasha’s Hideous Laughter or heightened Evard's Black Tentacles³ is very powerful, but no metamagic will make Flame Blade great.

This just can't be answered unless we see the whole list for all archetypes, but than it might be too broad.

Try to fit all possible metamagics on the spells, and if it still does not look overpowered, you are fine.

^{1. Sorcerers know 15 spells on level 20.}

^{2. The difference is even less, you could just cast something completely different like Toll the Dead or Haste.}

^{3. I think named spells (Evard's, Tasha's) are usually created stronger, because they are unavailable for Sorcerer's. Consider them a Wizard class feature compensating for no metamagic}