Your sentence 'Steve said to us that he was arriving at 8.00' is more emphatic than the two corrections, i.e. something you might say if you wanted to emphasize what it was that Steve said. It's something you might hear in spoken English, but it isn't good usage, as the use of the present continuous 'arriving' is confusing. You could substitute 'is' for 'was' and it would work. This is because you are referring back to what Steve said in the past about a future action, and are now quoting (in the present) what Steve said (in the past), but if you wanted to keep the emphatic quality of the sentence you could also say 'Steve said to us that he was going to arrive at 8'. More usual however would be constructions like 'Steve told us he: would arrive at 8/would be arriving at 8/will be here at 8'. In spoken English the 'that' is often left out.

Sorry, your teacher was correct. Your sentence was wrong. 'Steve said to us that...' is very strange. Some people might think it's 'grammatically ok' or whatever, nut it's wrong because NO ONE would say that. 'say' is not used like that. You have 2 very common options: Steve told us he was.. or Steve said he was.. (using 'that' is not necessary in simple sentences)

You can track the popularity or use of different phrases in written English using the Google N gram viewer, the results for your corrected phrase for example show a rise and drop off over time, try typing the phrase in here: https://books.google.com/ngrams

Your option is correct, as you suspected. Your teacher is focusing on the fact that tell needs a direct object but say cannot have one. Of course, say can have an indirect object (like "to us"). It would be necessary to add "to us" in cases of possible confusion (to us, not to them) but otherwise, there is no need for it.

P.S. If you had to make the top of the best corrections what correction would be the best? The 2 prize correction and 3 prize correction? Personally I think perhaps the super natural and best correction is Steve told us that he was arriving at 8.00. Then goes Steve said that he was arriving at 8.00. And my correction is possible, but it appears it is not so good (or it's not good at all), "Steve said to us that he was arriving at 8.00." Thank you!