Can one eat on Sunday if he hasn't heard Havdalah yet? If not, what happens if he already ate: should he say Havdalah?
The Aruch Hashulchan 299:16 quotes a dispute between all of the "heavy hitters" over the correct version of the g'mara in P'sachim 107. He quotes the opinion that when one recites havdala late (after dawn of Sunday morning), he only says borei p'ri hagafen and hamavdil ben kodesh l'chol (i.e. the non-whited-out parts here). And he only recites these b'rachos if he has not yet eaten. This appears to be the opinion of the Baha"g.
He quotes most others, including the Ram"a, who hold that one may still recite havdala until (and including) Tuesday even if one has eaten.
And to answer your first question, since the person is practically still waiting on Sunday to recite havdala, which is a mitzva, it should be treated like any other limited-time mitzva in that other activities (most prominent among which is eating) should not intervene.
Per Rabbi Doniel Neustadt if he will have wine before Chatzos on Sunday he should preferably wait and not eat unless he is weak.
Per Orach Chaim 299:5 you can make Havdala even if you ate already. The Mishna Berura says this applies even if the eating was done intentionally.
Havdala can be said till Tuesday if not said for some reason prior to that. (Rambam Hilchos Shabbos Perek 29 Halacha 4)