You are asking an excellent question. I see that the Minchas Chinuch offers a number of explanations for why that Nochri was given capital punishment:

1) Stealing is one of the seven Mitzvos Bnei Noach (Sanhedrin 57a; Rambam, Hilchos Melachim 9:9), and this Nochri stole a portion of the Korban Pesach. This is based on Rashi (Kidushin 52b, DH Ki, and Bava Kama 12b, DH Aval) who maintains that a Korban -- even after being slaughtered -- is still Mamon Gavoha. Only a Jew -- who has a right to eat it -- may partake, but for a Nochri who has no such right, taking part would constitute theft (Minchas Chinuch 14:2, DH Od).

2) The opinion of some Rishonim (the Semag, and possibly the Rambam) is that when a Nochri eats from the Korban Pesach, he is violating the prohibition of "Toshav v'Sachir Lo Yochal Bo" (Shemos 12:45). According to this view, it can be argued that this Isur is binding on a Nochri even though it is not listed as one of the seven Mitzvos Bnei Noach. The reason being because this prohibition either (a) is not applicable at all times, or (b) is not applicable in all places, or (c) is written openly in the Torah (Minchas Chinuch 14:1-2).

3) Possibly, when the Chachamim investigated this Nochri, they discovered that he was in violation of any number of the seven Mitzvos, and it was for those that he deserved the death penalty. This is like the answer which the Ramban (Bereishis 34:13) suggests regarding why Shimon and Levi were entitled to kill out the inhabitants of Shechem (Minchas Chinuch 14:2, DH u'Lich'orah).

4) I would like to share a few additional points with you:

a) Some Mefarshim take a totally different approach and maintain that the prohibition for which the Nochri was liable the death penalty was that of entering the Azarah. See the comment of the Netziv in his Meromei Sadeh (DH Badku). This could be a problem because of the Nochri's bodily Tum'ah, and/or because there was a law of the king (Hurdus, for example) that forbade a Nochri from entering too far into the central area of Har ha'Bayis.

b) Some suggest that the Nochri was guilty of "stealing" from the Jewish members of the Chaburah with whom he ate. See Rav Elchanan Wasserman zt'l Hy'd in his Kovetz Shi'urim (#6). Others point out that this Terutz will not necessarily hold up if we assume the Nochri paid fair and square for his portion. This is because there are Rishonim who maintain that paying for an item actually removes the Isur Gezel (see Tosfos in Bava Kama 62a, DH Chamsan, and in Sanhedrin 25b, DH me'Ikara). But others argue and hold that there is still an Isur Gezel even if the "thief" pays (view of the Ri Migash). It may be that only according to the latter view would the Cheshbon of the Netziv remain solid. See Rav Shmuel Rozovsky in Chidushei Rebbi Shmuel (#30).

c) As I alluded to above, not all Rishonim agree with the premise that a Nochri himself is violating the law of "Toshav v'Sachir Lo Yochal Bo" when he eats from a Korban Pesach. According to some, it is only the Jew who is violating that Mitzvah. In that case, it would be debatable whether the Jewish people could take the life of a Nochri in order to facilitate the Jews' observance of the this law.

I hope this helps!

Yishai Rasowsky