tsala

[Tanri]

The fact that the person could not see the other shore of the sea caused him to think that the sea never came to an end.

You got the meaning perfectly.

"That the person who gave the message to the clan leader finally realized that he had delivered just part of the message"

- hmm, even in this original text I not see the opportunity for tsala.
The word "that" seems to be unnecessary, so this is how I understood:
The person who gave the message to the clan leader, finally realized that he had delivered just part of the message.

Main clause is marked blue, red color shows me the attributive subordinate clause connected to the noun "person". The red clause is inserted into the main one.
Finally, the orange color marks another subordinate clause, which is connected into main clause like one big object (the thing realized).
While I know the famous rule "Translate the meaning, not the words", I think that Na'vi version should follow at least the same structure of the sentences (it may look different due to free constituent order):
Tutel a poleng 'upxaret olo'eyktanur, nì'i'a zerok futa pol poleng hapxìt tsa'upxareyä nì'aw.


Too slow I was, as always, but using another verb, there actually IS some tsala opportunity:
Tutet a poleng 'upxaret olo'eyktanur, nì'i'a vingkap tsala pol poleng hapxìt tsa'upxareyä nì'aw.

Tìsung: Ma Blue Elf, fpìlfya oengeyä zene livu steng nìngay, taluna oengal ftxoley meopinit ateng!

[Tirea Aean]

The fact that the person could not see the other shore of the sea caused him to think that the sea never came to an end.

You got the meaning perfectly.

"That the person who gave the message to the clan leader finally realized that he had delivered just part of the message"

- hmm, even in this original text I not see the opportunity for tsala.
The word "that" seems to be unnecessary, so this is how I understood:
The person who gave the message to the clan leader, finally realized that he had delivered just part of the message.

Main clause is marked blue, red color shows me the attributive subordinate clause connected to the noun "person". The red clause is inserted into the main one.
Finally, the orange color marks another subordinate clause, which is connected into main clause like one big object (the thing realized).
While I know the famous rule "Translate the meaning, not the words", I think that Na'vi version should follow at least the same structure of the sentences (it may look different due to free constituent order):
Tutel a poleng 'upxaret olo'eyktanur, nì'i'a zerok futa pol poleng hapxìt tsa'upxareyä nì'aw.


Too slow I was, as always, but using another verb, there actually IS some tsala opportunity:
Tutet a poleng 'upxaret olo'eyktanur, nì'i'a vingkap tsala pol poleng hapxìt tsa'upxareyä nì'aw.

YES. Big karma.