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.
“Europe” and “Asia” as distinct cultural units are defined by Herodotus almost at the beginning of his histories.(1.4.4: τὴν γὰρ Ἀσίην καὶ τὰ ἐνοικέοντα ἔθνεα βάρβαρα οἰκηιεῦνται οἱ Πέρσαι, τὴν δὲ Εὐρώπην καὶ τὸ Ἑλληνικόν ἥγηνται κεχωρίσθαι. ) Herodotus lived in the 5th century BC.
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?
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.