Does "Kupujemy od tego mężczyzny jajko" not sound natural or why is it marked wrong? In another exercice there is "Dostaję od niego ubrania" so I thought this order would work here aswell
You are right, it should work, it sounds perfectly normal. It just says "what we buy from this man" instead of "whom do we buy eggs from". Anyway, added, of course.
This seems to be genitive. Was "od" not supposed to be followed by locative?
No, "od" always takes Genitive.
Kupujemy jajka dla tego mężczyzny?
That means "for this man".