The most concise way that I've found to express this is:
Verbs that indicate the SUBJECT'S movement from one point to another (gehen, kommen), change in fundamental being from one state do another (werden, sterben), or a lack thereof (bleiben) will always use sein.
Now, when I say "a change in fundamental being," I mean things like growing, dying, transforming, becoming, etc. Actions like sleeping do not count.
Also note that transitive verbs always use haben, even if they fall into one of their categories. Do if you're walking your dog or growing a flower, you would use "haben." We're looking at the subject of the sentence to see if he, she, or it is undergoing the change. This is why "fahren" is so tricky. Whether to use sein or haben depends on whether you want to express that you moved from point A to B with a vehicle (sein) or you operated a vehicle (haben).
Transitive verbs must have a direct object. An indirect object does not matter. Many verbs that take an indirect object also take a direct object, but not always.
"gekommen" is not a transitive verb. http://dictionary.reverso.net/german-english/gekommen
Actually "uns" is in the Dative case, which does not necessarily mean that it is an indirect object, although indirect objects are also in the Dative case.
"uns" is not an indirect object. It is the object of the preposition "mit" Some German prepositions require Dative case. Some German prepositions require Accusative case. Some can take either for different meanings or to show movement rather than location. A few prepositions take the Genitive case.
http://german.about.com/library/blcase_dat2.htm http://german.about.com/library/blcase_acc2.htm http://german.about.com/library/blcase_gen2.htm
Please remember that the present perfect tense is the most common way to express what would be the simple past in English. So in 9 cases out of 10, "He came with us," would be the preferred translation.
When speaking to German friends about what you did today, you will always¹ use the present perfect: "Ich habe gegessen, ich habe geschrieben..." This is where literal translations fail. English would use the simple past in this case. Present perfect changes the meaning entirely.
If the German speaker intends to explicitly convey the same meaning that is conveyed by the present perfect in English—that is, "He has come with us (at least once in the past, but not an any specified time in particular,)"—they would be more likely (but not guaranteed) to include a qualifying word, such as mal, einmal, ein paar mal, or irgendwann.
So while you're not wrong, it would be unwise to equate the German present perfect with the English present perfect. It could lead to loads of misunderstanding in conversation.
Personally, I would require my students to translate this as, "He came with us," unless the context makes it clear that it should be, "He has come with us." Despite the latter being more literal, the former is FAR more likely to be accurate.
¹Exceptions are the verbs haben and sein, which are typically used in the simple past when spoken.
Native English speaker here (UK) and you could definitely say 'he has come with us' in some situations, especially if you're using it with modifiers. Consider, 'he has come with us a few times in the past', or (when arriving somewhere and gesturing to an individual for the benefit of others in the group who don't know him yet), 'Everyone, this is Ernst. He has come with us today to help break into the safe.' In UK English, at least, both formulations are grammatically correct.
I think you're getting downvoted because you said, "never," but I agree with the rest. I am a German teacher, and I can say with 100% confidence that the simple past is indeed, "a more natural translation, if less literal."
However, there's always the chance for that occasional instance in which the English present perfect is more appropriate.
I just want people doing this lesson to know that without context, the English simple past (came) is going to be more appropriate than the present perfect (has come) about 90% of the time. If you choose to ignore this rule, you're going to run into misunderstandings with natives. I speak from experience.
I'm from the U.S. and I can agree with Twoquiche regarding the usage.
However, because of the German quirk of using this tense to refer to the past, I'm not sure whether it's a better or even a good translation...
(...also curse you, verb forms unreasonably similar to things (is coming) that are not your proper translation... grrr X) no, I'm just a bit frustrated by trying to get my head around that part )
For one, you misspelled, "coming." But the more likely reason it was rejected is the fact that "He was coming with us" is past-progressive (Past tense form of "He is coming"), not present-perfect. Such a tense doesn't exist in German, at least not outside of certain nonstandard dialects.
"He has come with us," is a correct translation, and it should have been accepted. But I should warn you that, "He came with us," will be the more appropriate translation in 90% of cases. The German present-perfect is equivalent to the English simple past the vast majority of the time.
I put the same, but after looking at the comments I can see why "He is coming with us" is wrong, but I totally agree that the suggested answer makes no sense.
EDIT: After 3 months and doing this lesson again I see that what Duo is trying to say is: "He has come with us." which is very close in meaning to "He came with us."