The firefighter said that smoke was coming from the kitchen.

Porque say y tell no se usan exactamente igual.

• say puede ir solo o seguido de una oración:
  • The firefighter said that smoke was coming from the kitchen.
• tell normalmente necesita decir a quién se le dijo algo:
  • The firefighter told us that smoke was coming from the kitchen.

Entonces, told that... por sí solo suena incompleto. Si quieres usar tell, debes agregar un objeto como me, us, them, the police, etc.

Sí, that se puede quitar en muchos casos.

• Con that:
  • The firefighter said that smoke was coming from the kitchen.
• Sin that:
  • The firefighter said smoke was coming from the kitchen.

Las dos opciones son correctas.
That introduce la idea reportada, parecido a que en español. En inglés, muchas veces se omite en conversación y en escritura informal.

Porque was coming está en past continuous y describe una situación que estaba ocurriendo en ese momento del pasado.

• was coming = estaba saliendo / estaba viniendo
• came = como un evento más puntual