What do you want to do with Call of Cthulhu?
I'd think somewhere in the 1660s, when there were just enough settlers that not everyone was known by name and the colonies were mostly random batches of cultists (in the archaeological sense, i.e. members of relatively small non-mainstream sects, but also potentially in the CoC sense - there'd probably be a certain amount of blurring that could furnish plot hooks).
I'd suggested New England because there's the historical wiggle room and known variables of Lovecraft Country in there, but if someone else wanted to explore, say, furnishing a Mythos explanation for how the Lost Roanoke Colony dropped off the map (did they get a local war declared on them? what did they do?) or colonial Newfoundland etc. I'm not adverse.
For stories, there's the Roanoke idea up there, but down in what'd become the Arkham area it'd be interesting - I use the word with a slight wince, but you know what I mean - to see colonists breaking stuff, in this instance the adaptations the natives had made to living around the existent weirdness (it's implied that Y'ha-nthlei was down there at something like "current" size before Innsmouthers built a village next to it, for instance - was there a pact for locals and feeple to ignore each other? Help each other in certain circumstances? What happens when a colonist shoots one instead of helping? What if everyone who knows how to keep those horrible tree-things they see sometimes outside the area where traplines are set dies of measles?), or living without existent weirdness until some fools from a congregation with a name like Starry Wonders plonks it down there like leadworking byproducts in the water supply.
A tenuous peace provides considerable tension to a more ordinary plot of "that village next to us seems to be suspiciously insular/eccentric/childless and someone has stolen my pumpkins/grandma/baby for Dark Rites" - especially as Native folk won't necessarily know what normal European behavioural patterns are like. ...and then there's witches! In the folkloric/pan-cultural sense witchcraft seems to be a kind of bad madness (as opposed to neutral- or holy madness), which means corrupted spiritual dealers aren't really on anyone's side and might stir trouble for their own devices. Which could be Very Bad if they show colonists eyeing up your home ground your village's weaknesses, for instance.
...or if they, the village priest, campaign to infuriate the locals into mass action that could be taken as a raid, and go all Lord Summersisle on that little shack church when the terrified incursors huddle themselves in for prayer and protection. Also bad! Either way, if preventing such a situation wasn't the plot itself, such a massacre is a) prime horror fuel and b) a level of sacrifice that could call up a lot for Investigators to deal with.
For characters, I think letting people pitch what they felt like would give the Keeper the best idea on who would fit with a relatively niche idea. You might get all Europeans, which'd be disappointing but better than giving a local slot to someone who turns out to be wholly lacking in sensitivity and/or desire to research. You might get all Narragansetts/the odd surviving Pequot assimilated to some other people but with divergent goals, which'd be really interesting and lead to a very different story angle. A good group of players on that would remember it forever.