"They climbed Mount Kilimanjaro and they got tired"
Translation:Wakapanda mlima kilimanjaro na wakachoka
That's much better for this example, especially since the "na" here is redundant (-ka- roughly means "and then").
Btw, you can start a narrative with -ka- if the context makes it clear that it is a past narrative (although this is less standard):
e.g. "Jana wakapanda mlima Kilimanjaro wakachoka." - Yesterday they climbed Mount Kilimanjaro and (then they) got tired.
The function of starting with -li- is to (otherwise) provide this context and specify the "starting" action for the narrative (this happened, and then this, ...).
There are a few other examples in the course of only using -ka- with no -li- first. Unfortunately they aren't used in context (no obvious past setting), so they aren't good examples and could definitely be confusing since they don't follow what is written in the Tips and Notes.
I entirely agree with your comment. I guess my point is, having supplied no context, Duo must not INSIST that the first verb be in the -KA- tense and INSIST that NA be used to connect the two verbs. They can offer their version as one alternative, but as you suggest, there are several other (perhaps better) alternatives that need to be accepted.