And if it's the latter, there's no reason why it couldn't be the outcome of a successful coup.
Remember that the colonists were
docile as sheep, or else it wouldn't have been possible to slaughter half of them. It's not even a case of Kodos hiring ruthless gunmen to mow down a mob: supposedly, the deaths were "without pain", as if he had the authority to tell people to take their suicide pills. Now, that works both with a religiously worshipped longterm leader and
a recently arrived messiah.
Having "Kodos" arrive rather than preexist serves two purposes: there are fewer people who "really" know him, and there's the chance that Kirk arrived with him, hence didn't dwell on the planet long without his parents (of whom only mom could have been with him there without becoming a witness, presumably - that is, she could have become a victim instead).
Having Kodos preexist blocks most paths for rationalizing the eyewitness business, is all.