First off, his assumption that it is Sunday does not mean the previous day was shabbat. So my initial thought would be that he wouldn't say havdala being that everything is a safek and this havdala would only be said as a remembrance.
Though, if his assumption was correct, and it actually is Sunday, the question becomes whether shabbos is defined as you keeping shabbat or the day itself. Following the former reason, since he didn't keep that shabbat (This is a machloket rishonim whether one who unintentionally breaks shabbat is considered a mechalel.) I think he wouldn't have any reason to say havdala since he wasn't "shomer shabbat" (according to some rishonim). Or, on the flip side, is there kedusha inherently on the day and therefore whether he kept shabbat or not he would still have to make havdala.
Regarding your title question, the shulchan aruch says to make kiddush then havdala.
ההולך במדבר ואינו יודע מתי הוא שבת מונה שבעה ימים מיום שנתן אל לבו שכחתו ומקדש השביעי בקידוש והבדלה ואם יש לו ממה להתפרנס אסור לו לעשות מלאכה כלל עד שיכלה מה שיש לו ואז יעשה מלאכה בכל יום אפילו ביום שמקדש בו כדי פרנסתו מצומצמת ומותר לילך בו בכל יום אפי' ביום שמקדש בו:
One who is wandering in the desert and does not know when is Shabbat, counts seven days from the day he realized he did not know, and sanctifies the seventh day with Kiddush and Havdalah. If one has sustenance, one is forbidden from doing any work whatsoever until he uses what he has, and thereafter one should do work each day, even on the day he sanctifies, to achieve minimal sustenance. One is permitted to walk every day, even on the day he sanctifies.