'From a new setting' is clearly a geographical reference. It also necessarily means something that hasn't been playable yet. The game's still CK2

p), so the setting's gotta be relevant.
This leaves us with two options:
1. Map expansion, or
2. More or less total conversion, i.e. just like map expansion except not connected to the current map. It would need to be relatively large to merit a 'new setting'.
Out of the above two:
#1 faces problems with relevance; all relevant areas are already in; India is the only remotely viable thing here to think about, but dragging the map further east would require Tibet and a good deal of Siberia, and it would be impossible to avoid putting China on the map;
#2 in addition to the need to create at least several dozen provinces faces obvious problems with new cultures, religions and so on, like someone has already said; ergo this just has to rely on existing lore, although on the other hand in some areas making things up would be less time and resource consuming than historical research and geographical imititation.
I can think about Arthurian legends, but there's already a Paradox game about that. And at least two mods. Perhaps something Germanic or Keltic in style. Doubt it though. Sassanid Persia crossed my mind, but you can't really have that without accounting for Byzzies.
Nothing sounds plausible here TBH.
So... a new starting date? An Otto I/Hugo Capet start would contain a lot of differences from either the 867 or the 1066 start. One could probably call it a new setting.
Alternatively, perhaps a game mode like Ironman. Perhaps taking randomisation a bit farther.
Srsly though,
A new setting...A picture that looks like the Wall...Westeros is a new setting...A Game of Thrones DLC maybe, just putting it out there.
Wouldn't be completely surprised...