This discrepancy was noticed by the Mishneh LaMelech in his Parshas Derachim Derech Mitzvosecha 4:487, and the Minchas Chinuch § 487, among others.
As mentioned, the Chinuch leaves out the mitzvah against a zar eating kodshim, and he replaces it with the prohibition against bringing the Pesach offering on a private altar. He brings this as Mitzvah #467.
The Mishneh LaMelech and Rav Yerucham Fischel Perla (in his comments to Sefer HaMitzvos LeRasag Lo Sa'aseh § 174) explain that the Rambam and others left this mitzvah out because they felt it was only stated for a specific time (following Shoresh 3), ie: when private altars were permitted. The question is, why did the Chinuch include it, especially since he was so loyal to the Rambam? This in addition to the fact that the Chinuch doesn't even acknowledge his deviation from the Rambam (and Ramban).
Rav Chaim Heller, in his introduction to his version of Sefer HaMitzvos, explains that soon after Sefer HaMitzvos was published and subsequently translated, mistakes began to appear. He cites the Responsum of Rabbeinu Avraham ben HaRambam (Maaseh Nissim § 2) to Rav Daniel HaBavli who asked why the Rambam counted the prohibition of bringing the Pesach offering on a private altar when the mitzvah wasn't for all time. Rabbeinu Avraham responded that there is no such mitzvah in the sefer of the Rambam and it's entirely a mistake. Rav Heller assumes that Rav Daniel HaBavli had a version of Sefer HaMitzvos with this mistake in it, and suggests that perhaps this mistake was also in the version the Sefer HaChinuch had. This would explain why the Sefer HaChinuch deviated from the Rambam that we have (although this is not a definitive explanation, it's the best I found).
(Credit to the Frankel edition of the Rambam for providing a lot of the sources.)
I subsequently found the ArtScroll version of Sefer HaChinuch points to a different approach to this discrepancy, found in Mayan HaChochmah by Rav Noach Chaim Tzvi Berlin, which is as follows:
The Chinuch noticed the Rambam left out all the laws of private altars, yet codifies the law prohibiting the Pesach offering on a private altar. This must mean that private altars are no longer relevant today as it is anyways forbidden to bring an offering outside the Temple. Since the Rambam specifically codified the law pertaining to the Pesach offering, that law must be relevant even today.
The Chinuch must also hold like Tosafos in Zevachim 59a, who say everyone agrees that someone today who slaughters an offering outside the Temple is exempt from kares. Therefore, the prohibition pertaining to the Pesach offering would be a novelty, punished by kares, making it fitting to count in the 613 mitzvos. However, the Rambam disagrees with Tosafos and holds slaughtering an offering today outside the Temple does get punished with kares. That means there's nothing unique about the Pesach offering. It's just an extra prohibition, which isn't worth counting in the 613.
All this explains why the Chinuch added this mitzvah, but not why he discounted a zar eating kodshim. The Mayan HaChochmah (I can't find where) says that the Chinuch held that that verse (Exodus 29:33) is referring to the miluim, the inaugural korbonos ceremony. Therefore, that prohibition was only for that time, and isn't to be counted in 613 (ArtScroll cites Maharam Schik #103 who also says this).
However, ArtScroll points out this is hard to understand, as the first half of that verse is counted by the Chinuch as a mitzvah, meaning not exclusively about the miluim. Why wouldn't this part of the verse be treated the same. They subsequently point to Maharam Schik #103 for a possible resolution, although I don't get how he resolves it (he says it's just a ייתור דקרא so not worth counting).
All of this fails to explain why the Sefer HaChinuch in both locations doesn't notify us that he's deviating from the Rambam.
Of course, the first explanation seems a lot simpler and is thus more likely to be correct.
