When was the concept of Europe as a singular political unit conceived? When did people start to think of themselves as sharing a similar European culture and calling themselves European? For this answer, I don't mean the Roman Empire or Christendom, as these include many areas outside Europe, but specifically "Europe." The EU would be a good example but I'm hoping for something much earlier.
Even today I doubt that there is such a thing like a "European culture". The cultural differences between different countries are huge. I'm not just talking about the difference between a Nordic country and a Mediterranean country, even neighboring countries like Belgium (where I'm from) and Germany are quite different, culturally. Much has to do with language: Germans don't understand Dutch or French, and many Belgians don't speak German. This means we have limited access to each other's theater or film scene, and don't watch their TV programs. Because of this the cultural difference between Flanders in Belgium and the Netherlands is much smaller (same language: Dutch), and we know each other better.
The unification of Europe wasn't spurred by cultural ends, but rather economical. After WW II (and I don't think it started much earlier!) there was the European Union of Coal and Steel as a forerunner of the European Economical Union. That says it all: coal and steel were more important that culture. Robert Schuman (regarded by many as the father of a united Europe) may have dreamt that culture would follow, but until now this didn't happen.
Just think: would the US feel as much of a union if in the different states they would have spoken 20 different languages?
There is a false premise in the question. Namely, Europe as a political unit has always been a step ahead of Europe as a cultural unit. I found this question while looking for information on an 18th century treatise that set out the benefits of a political union in Europe -- which as far as I know is the earliest that this idea was espoused in this way.
Yet, this doesn't mean that there's a unified European culture. Even now, there are 27 different cultures, all of which have a state ('nation state' in many cases) that altogether form a single political union.
Nevertheless, my answer to the question 'When was the concept of Europe as a singular political unit [first] conceived?' is in 1767 and by Jakob Heinrich von Lilienfeld in 'Neues Staats-Gebäude, in drey Büchern'. The title, 'Neues Staats-Gebäude', is difficult to translate (for me), but I'd opt for "The New Structure of the State". WP describes this treatise as:
Die in seinem Werk „Neues Staats-Gebäude“ aus dem Jahr 1767 beschriebene Idee eines europäischen Staatenbundes mit dem Ziel der zwischenstaatlichen friedlichen Streiterledigung vor einem europäischen Gerichtshof fand in der zeitgenössischen Staatsrechtwissenschaft lebhaften Widerhall, geriet dann aber in Vergessenheit und wurde erst 1997 wieder entdeckt. Der Kernpunkt seiner Vorstellung bestand darin, die damalige Willkür der Fürsten einzuschränken. Er entwarf einen Friedensentwurf für ein friedliches, freies und föderatives Europa, in dem ein Gerichtshof die Macht der Herrscher insoweit einschränken sollte, dass sie die Völker durch Auspressung und Kriegsfolgen nicht ruinieren können.
Google Translate (slightly modified):
The idea of a European confederation, described in his work "Neues Staats-Gebäude" from 1767, with the aim of settling peaceful disputes between states at a European court, met with vigorous resonance in contemporary constitutional law, but was then forgotten and was only rediscovered in 1997. The main point of his idea was to limit the princes' arbitrariness at that time. He drafted a draft peace for a peaceful, free and federative Europe in which a court of law should limit the power of the rulers to such an extent that they cannot ruin the people through expression and the aftermath of war.
The Estonian WP adds that Tavares da Silva's book 'Europe, giving shape to an idea' also mentions von Lilienfeld and his idea. The Google Books preview for that title is severely limited (at least in my location) so I am not sure what exactly is included there.
While "vigorous resonance" is mentioned above, von Lilienfeld seems to have been generally forgotten. The question I was investigating was how much the European Coal & Steel Community founders knew about him, which the German Wikipedia kind of answered (as in, "they didn't" until being "rediscovered in 1997").
This site also has some further background (not been mentioned elsewhere):
Seltene einzige Ausgabe des wenig bekannten Werkes zur Einigung Europas! Der großangelegte und detaillierte Entwurf eines zukünftigen Europas sieht die Einrichtung eines Friedensgerichtes und einer gemeinsame geführten Armee aus multinationalen Streitkräften, sog. "Orden", gegen außereuropäische Bedrohungen wie das Osmanische Reich vor. - "Meine Entwürfe mögen immerhin den Leser befremden und den Verfasser lächerlich machen. Christoph Columbo und diejenigen, die zuerst die Gegenfüßler und das Umdrehen der Erde lehreten, hatten ein gleiches Schicksal" (Vorrede). - Lilienfeld (1716-1785) stand als Geheimer Legationsrat in holsteinischen Diensten und gehörte einem Kreis von aktiven Aufklärern und Unternehmern in Pöltsamaa/Oberpahlen (heutiges Estland) an, der die politische Reform und wirtschaftliche Modernisierung Russlands anstrebte.
Google Translate (slightly modified):
Rare only edition of the little-known work on the unification of Europe! The large-scale and detailed draft of a future Europe provides for the establishment of a peace court and a jointly led army of multinational armed forces, so-called "orders", against non-European threats such as the Ottoman Empire. - "After all, my designs may alienate the reader and ridicule the author. Christopher Columbus and those who first taught the Antipodeans and of the revolving of the world had an equal fate" (preface). - Lilienfeld (1716-1785) was a secret legation council in the service of Holstein and belonged to a circle of active enlighteners and entrepreneurs in Põltsamaa / Oberpahlen (today's Estonia), which aimed at the political reform and economic modernization of Russia.
Insofar as I know, this is the earliest comprehensive suggestion of a (con)federate European state.
I think it goes throughout history, and I'm inclined to include the examples that you've excluded that is European Christiandom and the Roman Empire. They're notions of continental unity on the ecclesiastical and political level. Periodically there had been revivals of the Roman political project, for example by Charlemagne.
The roots of European culture is generally seen in three different orientations - the Hebrew prophetic tradition, the Roman civic tradition and the Greek philosophy.
The EU was concieved as a project to prevent inter-state aggression within Europe following the catastrophe of the first two World Wars. The strategy one discerns was initionally economic (the Union was originally confined to multi-lateral agreements on Steel and Coal) and then political.
Of course, Turkey has been petitioning the Union for incorporation for at least the last decade. Historically, the roots of the Greek philosophical tradition (usually known as the Pre-Socratics), lay in the Greek periphary - the Colonies; Miletus materialism was formulated in the Colony of Miletus a colony in what is now North Turkey and via Lucretious De Rerum Natura (Newton had a heavily annotated copy) is one of the roots of modern science.