2 possibilities for the origin of the Na'vi are posed on the Na'vi page of the Avatar Wiki:
From the evidence, one may conclude that the Na'vi either diverged a long time ago from the common Pandoran phylogenetic or evolutionary tree, or they may be outsiders to this world.
Hashem must have wondered about this Chakirah (question), and in order to support the first Tzad (opinion), wrote that they arose before Moshe Rabbeinu. According to this, "Lo Kam Na'vi" does not mean that they will not arise in war, but rather that they did not come into being as a nation after that time.
In fact, Avraham (and various other later figures in Tanach) was a Na'vi, as it says in Bereishis 20:7:
וְעַתָּה הָשֵׁב אֵשֶׁת הָאִישׁ כִּי נָבִיא הוּא
(Additionally, they occupy such as special place in Hashem's heart that they are the reason why Techeiles is blue, as it says in Meshech Chachma Devarim 34:
תכלית ההשגה מה שלא קם נביא
Techeiles is reached because another Na'vi will not arise.