Lets approach this from real world biology, assuming the existence of the parasite and desired effects.
1: How do The Parasites Acquire Genes?
Horizontal gene transfer! Happens all the time in bacteria. However acquiring a gene doesn't mean it's useful or helpful. That's why your degenerates stop expressing gendered features.
2: The Various Effects on Degenerates?
The infection replaces key parts which are essential for the degenerates to survive and reproduce on their own. But that's not important, it's the parasites reproduction that has the evolutionary pressure. Things that impact the parasites fitness are what matters here. Degenerates don't have babies, and parasites infect normal humans, so why keep gendered traits?
As long as the parasite can continue to reproduce, they don't need to worry about preserving those parts of the genome during infection.
3: Laying eggs
The parasites lay them, using the resources of the host, this is how parasites work in the real world. Otherwise, it isn't really a parasite, more like a virus.
4: The Fjǫlkynngi gene?
Just because your genes code to create a Giraffe doesn't mean you turn into a Giraffe. Perhaps if your genome was replaced during the zygote stage you might follow that development process, but in adult humans this process has already happened. So you're much more likely to die within a day or two than turn into a giraffe.
Now lets say the parasite acquired this gene, and transmitted it to a degenerate, that doesn't mean the genes effects somehow apply
This does mean however that if somebody who already has this gene is infected, then the infected magic user can use magic. That would explain your kings.
So all you need is for the gene to result in an organ or developmental change.
This also means that the gene transferral might be successful if a parasite transforms a pregnant woman during the early stages of development.
5: Why Don't They Just Evolve to Bypass This?
There would probably be a lot of evolutionary pressure for the Degenerates to evolve toward a species-wide acceptance of the Fjǫlkynngi gene. So why haven’t they?
That's not how evolutionary pressure or selection works. Given a population, traits that help them survive are more likely to be passed on, and traits that make them less likely to survive aren't.
There is no guidance towards particular features, your genome doesn't look at other creatures and decide it wants one of their traits. For them to evolve acceptance of that genes benefit, they would need to have some accidental mutation that conveyed a slight survival advantage in that direction, combined with successful reproduction.
If another mutation conveyed a stronger version of that manifestation then it would result in a greater chance of reproduction, and so on until you've arrived at the goal. Not all mutations will lead in that direction though. Genetic mutations happen all the time and they have no effect or cause disease.
And that's why your degenerates didn't just evolve to use magic.