Would "Der Mann isst nicht mit ihrem kind" be an ok translation here?
No. The word is "his" and sein is the only acceptable answer. Ihrem would be "their"
It's "seinem" (and not :seine") because "Kind" is neuter?
Yep, plus it's dative, hence the -em ending, and not something else.
Why does "bei" not work as well as "mit" here. Would that only mean he is eating at his child's house?