The rules as written don't say specifically.

"Immune" doesn't carry any special meaning in 5e. An ordinary language interpretation of "immune" would be that a character immune to disease can't contract any diseases, and that any diseases they have are immediately cured.

The DM may rule otherwise, although at the very least it would seem reasonable that such a character would not suffer any further negative effects from the disease, and that they would automatically succeed at any future saving throws the disease calls for.

It is also up to the DM to rule if immunity to diseases removes any scars or blemishes that previous diseases may have inflicted, or if more serious permanent effects of diseases (for example, blindness from sight rot) are healed.

My reading of the rules as intended is that 3rd level paladins gain an advantage in the 'exploration' pillar of the game by ignoring a specific class (diseases) of environmental hazards. As such, I would expect that once they gain 3rd level, any negative effects of diseases are completely removed.

Not likely, but a case could be made for it

This is a bit of a tricky area, but in general we have go with the idea that things do what they say they do and no more. As with all things 5e, a DM can choose to view it differently, but looking at it through a RAW lens implies that the Paladin would still suffer the effects.

The case for Infestation

As I stated above, in 5e things (like spells) generally do what they say they do and no more. There is no clause in the Spawn of Kyuss that states that creatures immune to Disease are immune to the effects of the Spawn.

In addition, the Spawn of Kyuss doesn't state that it is a Disease. Just that using something that cures Disease will force them to wither away.

The case for Immunity

This piece comes from the viewpoint that much in the same way that a creature who is immune to certain conditions (like Charmed) makes them immune to spells that cause that such a condition.

There are a myriad of examples that show that being immune to a condition makes you immune to an effect (e.g., creatures immune to Frightened are not affected by a Vengeance Paladin's Abjure Enemy). Or that creatures immune to Charm are not affected by spells/abilities that Charm them.

The logic here is that if curing a disease kills the Spawn, and a paladin is immune to disease, then why would this 'disease' be active in it's body?

It's a reasonable step, but it isn't totally supported by RAW. A DM could houserule that as there is some sense to it, but I do not believe this to be RAW, however it may be intended.