This is not a sentence, but an argument (as the later question 'Is the argument valid?' also indicates) involving multiple sentences. So you really shouldn;t symbolize this with a conditional, but instead have three separate sentence, 2 premises and 1 conclusion.
Also, you can take out the $Fx \lor Mx$ part: it says 'everyone', so it should be everyone, and if you are concerned about gender-neutral persons, this sentence clearly is not, since it continues with 'his or her'. So yes, you would be right that this would be invalid if only "he"'s and "she"'s have parents, and that there might be people who are not either "he" or "she', but the sentences clearly assumes everyone to be a "he" or "she". So: you can either add the $Fx \lor Mx$ part to every sentence, or (which would be my preference, since with the assumption that everyone is a "he" or "she", the $Fx \lor Mx$ part ends up saying nothing of interest) leave it out completely.
So, this leaves you with:
$\forall x \forall y (Pyx \rightarrow Lxy)$
$\forall x \exists y \exists z (Pyx \land Pzx \land y \not = z)$
$\therefore \forall x \exists y \exists z (y \not = z \land Lxy \land Lxz)$
... which is easily shown to be valid.