Imho the problem of creating an european
empire, to which many have proposed solutions, is not the same as that of creating an european
nation.
The two are, to some extent, antinomic. Without diving into the theory details, nationhood is closely tied in with modern statehood. Sovereignty and the formation of an imagined community, to give only two examples, are "provided to the nation" by the existence of a modern State; inversely, nationhood provides a basis for acceptance and support to the State. That is not to say that empire and nationhood cannot coexist, to the countrary: the Russian and British national consciousness both developped on the basis of their nation leading an empire. However, you cannot just assume that the empire will just become a modern State and all of its people will happily identify with the same nation. An example of what I mean is again given by the British and Russian empires, but also by the Ottoman empire, in the XIXth century, where the modernisation of the empire into a modern State was paired with the development of a national consciounsness for the leading people, on the one hand, and of other consciousnesses for the subaltern peoples. The same is true if we wank another early european empire, be it the Hohenstaufen, Rome or (kudos for originality!!) Samo's Kingdom. Even if we wank Frederick II into achieving his wildest dreams of
dominium mundi, we still have to explain how the Empire's ideology will transition from triumphant christian universalism to german nationalism: if Frederick is lording over Jerusalem, Palermo and Rome as well as Anvers, Aachen and Hamburg, how would his successors come to see their empire as "german" and how would the people of the empire acquiesce that this makes any sense? We're just headed for a re-run of the ottoman collapse once the empire heads into the XIXth century. Empire-building is easy compared to ethnogenesis.
@Socrates makes the crucial point that an empire doesn't become a nation overnight as well. But I'd argue the chinese case is an exception, because of an interplay of its long-term history - the 1911 revolutionaries inherited a country that had been , on paper at least, united around a single cultural model since the Song at least, with no alternative cultural model for the elites - and of the particular flavour of Chinese nationalism - which developed both in the empire and
against the empire in the sense that radical nationalists advocated for the ousting of the "foreign" Manchus. So if we want to reenact a similar process in Europe, we need either to suppress the cultural diversity of Europe from the high middle ages onwards, at least within the empire - good luck - , or to build an empire that is not only extensive but extremely long-lived, or to bring it into a particular situation of domination by a "foreign elite". When I say "or", I mean all these changes combined are probably necessary. Overall, when you add up all the changes needed to make Europe follow the same route as China, you end up with something that doesn't look like Europe at all.
Imho, while we can wank States in the premodern era a bit (as long as they stay under the "empire" threshold and stay compact & centralised enough that they can transition into modern States), the easiest way is to act upon the early stages of the formation of modern States & Nations in the late XVIIIth - XIXth centuries, while national identities were still fluid. I think France is our best bet, for a number of reasons: it is already a rather large nation, it has historically had a rather open conception of citizenship (in 1800 or 1900, it was way easier to become - nominally - French than German), and it underwent a period of expansion just at the point when it transition into moden State- and nationhood.
Let's say France has a slightly better early modern era, taking bits of Catalonia or the Rhineland in the XVIIth century for instance, and then the Revolution succeeds in keeping hold of the left bank of the Rhine. Since the Revolutionaries' conception of nationhood at this point was still based on citizenship and german nationalism wasn't whipped up yet, I suppose all those people in Catalonia, Belgium and the Rhine will assimilate. We end up with more or less a hundred millions French people today, which isn't that bad. I'd like to see the repartitions of seats in the EP with the French making up 1/4th of the EU's population.
There are also some more wildcards scenarii. First, there's the western Slavs option, but I wouldn't put my money on it since the unsuitability of the PLC for transitioning into a modern State and united nation makes it necessary to rewrite the entire history of the region from at least 1400 onwards. Probably earlier, since the Lithuanians had a well-established State and identity by then.
Second, you can "cheat" by toying with demography. If you delay the french demographic transition, or if you decrease the population of some parts of the continent as some have suggested, you end up with different results. I think you can integrate demographic variables in a AH scenario, but I find purely demographic scenarii arbitrary.
Third, you can envision a degree of successful colonial assimilation. I'm just mentioning it, since the odds of it succeeding are at least as low as in the other imperial cases, and this is not what the OP had in mind.