>We resolved the situation that this city would have needed to reduce it's population to 5 when the next phase 4 of a game turn occured.
Well, I think the rules are very clear on what happens without having a "what happens when a marketplace is destroyed" rule. Cities which have 5 (or more) citizens, do not get population growth. But nowhere is it implied that cities will be reduced in size for this reason.
Since it cannot grow, it is probably doomed in later turns (which there were none in your game).