Exactly. You have to take one province from them, and then vassalize them in the next war. Or make them release some minor. You can switch culture in enemy colonies as long as they are colonies by sending another colonist there, and afterwards via decision up till a certain size, which you are asking for but i sadly don't know. But from your description i assume it is still a colony?
As I thought.
And again, I'm double-checking here - you can annex a capital if you take every province around it, correct? So if I eat the huge infamy spike for gobbling the provinces around Novgorod, I can annex Novgorod the province next war and vassalize the remaining country so I can score the core (from mission) and the province and thus proclaim myself Russia (I already have everything else)?
As for Kola, yeah, it's still a colony right now, they only dropped in a few months ago.