(these answers, IMO, also apply to the Monk's Purity of Body)
RAW: Paladins are probably susceptible to Kyuss Worms
Because of… Reasons. 5th edition did away with a lot of verbose text present in previous editions, in favor of "plain English interpretation". With that, we get a fallout of precise text that can be pointed to with that triumphant "A HA!" that we all like.
RAI: Paladins are maybe immune to Kyuss Worms
To quote myself from just earlier,
5th edition did away with a lot of verbose text present in previous editions, in favor of "plain English interpretation"
If the ability can be removed with Remove Disease, then it probably counts as a "Disease".
So, what's a disease?
dis·ease dəˈzēz
noun
a disorder of structure or function in a human, animal, or plant, especially one that produces specific signs or symptoms or that affects a specific location and is not simply a direct result of physical injury.
Since we don't have a "diseased" condition in 5th edition, let's look at effects that call out disease in the Monster Manual.
- Aboleths (mucous and tentacles)
- Gas Spore (death burst)
- Otyugh
- Blue Slaad (Chaos Phage)
- Death Dog (under it's bite, it actually says "become poisoned")
- (Variant) Diseased Giant Rats (Bite)
And I saved this one for last: Red Slaad:
Claw
…DC 14 Constitution Saving Throw or be infected with a disease – a miniscule slaad egg…
A parasite that is inserted into the creature and will eventually kill it, is a disease.
So, that's 6-7 monsters in the MM and there are a couple references of "how to create diseases" in the DMG (p 256). Divine Health is an ability that doesn't get a ton of usage anyway and there's a precedent for an infestation of parasites to be counted as a disease…
Which brings me to:
RACS: Paladins are definitely immune to Kyuss Worms
An "always on" effect shouldn't be bypassed by a minor grammatical snafu of the word "targeting".
If a Fire Elemental was attacked by something that had text like:
"If a fire-worm-infested creature is targeted by an effect that bestows resistance or immunity to fire damage, all the fire-worms infesting it wither away.
You likely wouldn't say "Well, the Fire Elemental's Fire Immunity isn't targeting it so… I guess he still has fire worms burrowing into his fire-skin. Sucks to suck."
If you look back to 1st edition AD&D (In the Fiend Folio), the text about "Cure Disease or Remove Curse" is an ancient throwback. The only thing missing is the text about "in 1d4+1 rounds, the worm burrows into the target's brain and it dies". This is a Monster that was created, partially as fan service, but also years after the original release of the core books.
I find it unlikely that the writers of Volo's Guide looked at the old Son of Kyuss statblocks, then at the PHB Paladin, then read through both and made a deliberate decision to word the worm infestation in such a way as to exclude Divine Health (and the Monk's Purity of Body, for that matter).
RAF: Don't surprise your players
If at your table, parasites don't count as a disease, then make sure your Paladin (and everyone) knows that. It would be taking advantage of your infinite DM-powers to withhold that information as a special "GOTCHA!" so that the Paladin gets a Kyuss Worm infestation when he feels that he should be immune to it.
At MY table? Let the Paladin shine just a little bit brighter. It'd be cool to have these worms fall onto the Paladin's skin and take a bite, only to burst in a *pop* of radiance and crumble to the ground. He's a chosen warrior of the realm. It should feel like it.
RAW: Rules as Written
RAI: Rules as Intended
RACS: Rules as Common Sense
RAF: Rules as Fun