Let's assume the colony was one of those isolationist refuges, founded so that the settlers could avoid contact with the Federation. That would give Kodos maximally free hands - as a charismatic, Sandoval-type leader, he could control communications, assemble death squads and exaggerate food supply problems.
However, such a colony would be highly unlikely to receive regular food shipments. And we'd prefer regular shipments over emergency ones, because as argued above, emergency ones should arrive pretty quickly. And it was specifically mentioned that the shipment that saved the colony arrived earlier than expected, which would be unlikely if it were an emergency mission - because an emergency mission would have to be summoned through communications, and consequently this mission would communicate back its arrival time.
So let's instead assume a colony on an almost uninhabitable planet that offers no alternate food, and relies on regular shipments that arrive many, many months apart even if the actual flight to the colony only takes a few weeks. A fungus then removes virtually all food, and Kodos exaggerates the problem, swaying a sufficient number of people to support culling instead of rationing as the survival method. But in that case, the colony wouldn't be completely isolationist, and should have a communications channel back to civilization. A fungus is an unlikely disaster for removing both the food supply AND the communications link. So Kodos ought to have been able to call for help, or then he had to engineer a further accident that removed communications - and history books would remember this suspicious occurrence, so Spock's story should not deal with a controversial leader who took drastic but possibly necessary action, but should instead expose a villain who arranged for the unnecessary deaths of 4,000 people.
It doesn't seem all that simple to find a Goldilocks version where regular supply ships and communications cuts/lags are logically combined.
We also have to ponder why nobody knew what Kodos looked like. If he were the governor of 4,000 angry survivors, his face ought to be familiar enough. And Starfleet wasn't exactly lacking in photos or even sound bites of Kodos anyway.
But we could assume Kodos was the nom de guerre of some virtually faceless nobody, perhaps a new arrival, who exploited (or arranged for) the crisis, deposed the original governor (a coup is mentioned in dialogue), and organized the death squads. At the conclusion of the horror, virtually nobody out of the 4,000 survivors would know the true identity of this person. And if "Kodos" really was a new arrival, we might argue that the nine eyewitnesses arrived together with him and thus had extra knowledge on his real, original identity - knowledge that could help establish his new identity as well, and thus help in tracking him down.
But new arrivals would imply a ship. Why did that ship dump young Jim Kirk on Tarsus IV and then depart? Or if the ship stayed, why did it not help the colony?
Perhaps Jim Kirk et al. arrived with "Kodos", and then sailed back to civilization, but "Kodos" remained behind, and then engineered/exploited the famine. Kirk, Riley and pals would not have witnessed the massacre (hence they survived it, even though "Kodos" would definitely have wanted all of them dead in the first volley), and indeed nobody claims that they would have - but they would be eyewitnesses to the identity of "Kodos", which is the actual claim made about them.
Hmm... A visiting ship, closely followed by a disaster. Perhaps the colonists believed that the disaster had arrived with the ship, and therefore did not trust outside help? A bit far-fetched...
The communications problem remains the most annoying inconsistency here. If ships really take their time to arrive, there could be a long distance involved, and thus a communications lag as well. But could the lag be almost as long as the ship travel time? That's basically unprecedented in Trek.
OTOH, it's well precedented (or postcedented) that loyal UFP members may refrain from communicating with the central worlds for extended lengths of time. Deneva, a colony of millions that was a crossroads, not a distant fringe world, fell silent at least a year before Starfleet deigned to pay it a visit!
One would still assume any colony would make contact in an emergency. But the silence from Deneva was accepted even though Starfleet did suspect an emergency. Are we to conclude that colonies in TOS lacked the means to send out a realtime SOS? A bit weird, technologically speaking, when Deneva sported at least one private "subspace ham radio"! Was it a range issue?
Timo Saloniemi