I think you may have incorrectly parsed the sentence, because you did not look at the preceding clause. It should be read as follows:
כל מקדש שביעי כראוי
Whoever sanctifies the Sabbath properly
לו כל שומר שבת כדת מחללו
To him, anyone who keeps the Sabbath according to the law desecrates it
Read this way the supposed paradox falls away. It's not making an objective claim that someone who keeps the Sabbath in fact desecrates it. The claim is, rather, that from the perspective of one who sanctifies the Sabbath properly, one who merely observes the law is as if he desecrated the Sabbath.
Now what are these two categories? These are explained in other Talmudic passages. In Megillah 12a we find:
מאי כדת אמר רבי חנן משם רבי מאיר כדת של תורה
What is "according to the law"? R. Chanan in the name of R. Meir said "according to the law of the Torah".
In Ketubot 3a we find:
כל דמקדש אדעתא דרבנן מקדש
Whoever sanctifies according to the Rabbis, sanctifies.
Thus we see from these two passages that שומר שבת כדת means that he fulfills the Torah laws of the Sabbath, while מקדש שביעי כראוי means that he also fulfills the rabbinic laws of the Sabbath. From the perspective of fulfilling rabbinic laws, one who only fulfills the Torah laws is indeed desecrating the Sabbath.