Translation:They just left.
No it's not a matter of formality. 他们刚走 = 他们刚刚走 (了 is not necessary and is optional; these two sentences are equal in terms of the amount of formality). Personally I would add a 了 in situations where I want to emphasize that they HAVE already left. For example if someone comes looking for them and I want to indicate that they are gone, I'd say 他们刚走了! Or if I want to emphasize that they have JUST left, I'd say 他们刚刚走 (without the 了). Again it's optional.
To respond to your concern about formality, 他们刚离开 would sound more formal. Source: native speaker
I object to the duolinguo translation for two reasons. Firstly it's ambiguous since it also has the meaning "all they did was leave!" And the second reason for my objection is that it is ungrammatical in at least one major dialect of English ie. British English where if you can use the present perfect, you must use the present perfect.
I don't understand your grammar point about the present perfect. Why would a simple past tense be wrong, e.g. "It rained every day"? Yes you can use the present perfect "It has rained every day", but it carries a different tense aspect. Both are correct in my opinion, as is the sentence here: "They just left".