Manual p.18 : "Random or Historical Names: This setting is self-explanatory. Even on the Historical
setting, however, many of the historical names are not really based strictly on history. This
is especially true in the New World."

I do not have this setting on the Preferences screen. Is it removed ?

Yeah I never saw it in the game. I would have liked it if the historical names were assigned before the Imperialism 1 names though, some province names are only ever seen on the rare occasion that the New World nations are given an abnormally high number of provinces.