Without a wish or divine/DM intervention, they are gone for good
First, some background...
Exhaustion levels are a bucket, not LIFO1
Here is what we know about Exhaustion:
Some special abilities and environmental hazards, such as starvation and the long-term effects of freezing or scorching temperatures, can lead to a special condition called exhaustion. Exhaustion is measured in six levels. An effect can give a creature one or more levels of exhaustion, as specified in the effect's description.
If an already exhausted creature suffers another effect that causes exhaustion, its current level of exhaustion increases by the amount specified in the effect's description.
A creature suffers the effect of its current level of exhaustion as well as all lower levels. For example, a creature suffering level 2 exhaustion has its speed halved and has disadvantage on ability checks.
An effect that removes exhaustion reduces its level as specified in the effect's description, with all exhaustion effects ending if a creature's exhaustion level is reduced below 1.
Finishing a long rest reduces a creature's exhaustion level by 1, provided that the creature has also ingested some food and drink. Also, being raised from the dead reduces a creature’s exhaustion level by 1.
And finally, as noted in the question, "Exhaustion caused by lack of food or water can't be removed until the character eats and drinks the full required amount."
How that works
When you cure a level of exhaustion, no where does it say you have to cure the last thing that gave you exhaustion.
As an example; The character goes for a forced march AND they don't eat so they starve. Each gives a level of exhaustion. So at the end of the day, they have two levels of exhaustion. They then camp for the night and eat and drink normally. This would reduce one level of exhaustion... But which one?
It doesn't matter! It just lowers the level by one. The character now has one level.
And because they ate and drank their normal fill, it removed the "can't be removed" stipulation. But what if they just used greater restoration? They could still lose one level of exhaustion, but they cannot remove that final level until they eat and drink.
With that said, your six-day-starved character is most likely perma-dead
In your specific example, the creature suffered from all six levels as starvation. So there is no level they can remove without somehow eating and drinking; a very hard task to do when dead. In which case, they are out of luck as the stipulation would stack across all six levels.
Here is were DM intervention/allowances comes in
Once dead, someone can cast animate dead on the character to bring them back. The spellcaster will then command the zombie to eat and drink a days rations2. Then someone needs to kill the character again. Per this question, you can use at least true resurrection (if not other resurrection spells) to bring them back as a non-undead creature.
Technically, they will have eaten/drank enough to be able to remove at least one of the eat/drink stipulation so when the resurrection is applied, it will also remove one level of exhaustion bringing them to level 5. Now with five more days of normal eating, drinking, and bed rest your character is back to normal.
Just realize this is well into the realm of DM fiat...
But in most all other situations, there is still a reasonable chance
If a character dies from starvation, as in, it added the sixth level, there is now a stipulation on their recovery; they have to eat and drink their fill at least once to remove one of the levels of exhaustion. But it doesn't have to be the FIRST level removed.
Someone can cast raise dead and now the character has five levels. The now alive character can now receive four greater restoration spells and be brought up to only one level; but they cannot remove that final level until "the character eats and drinks the full required amount."
1 Last In, First Out
2 Undead creatures say, "doesn't require air, food, drink, or sleep." They don't require eating, but it doesn't stop them from going through the motions.