Most Europeans share recent ancestors
It looks like I will have to retreat to the position that there may be
some people who aren't related to Charlemagne (or we can choose a different ancestor because Charlemagne's DNA will have received preferential treatment).
The argument
@CGSwans uses about 1 quadrillion ancestors for 50 generations makes me uncomfortable. For 25 generations that number drops to 30 million. That's conveniently the population of Europe at the time of Charlemagne. To put that another way, if we assume the population stays constant, and we might get away with that, even if Europe was just one large body of people freely interacting it would take 600 years for one individual's DNA to propagate throughout the continent. But if we model Europe as a series of smaller population fragments, with periodic exchanges of random DNA, then the higher growth rates 'up' the curve of exponential growth become less and less available.
I'm going to try this out, and see.