According to professor Klaus Oschema, Europe was not used as a synonym for "Christendom" or "Christianity". This is a verbatim quote from the English abstract of his book Bilder von Europa im Mittelalter [Images of Europe in the Middle Ages], (Mittelalter-Forschungen, 43) Ostfildern, 2013. I do not know if an English translation is available, but if you are interested in this matter and feel confident with your German, this book is a must-read.

In this answer I will try to reassume some of the points also made by Oschema, though I hope you will pardon me if I do not stray into the High and Late Middle Ages, and stick close to Early Medieval Latin authors, which are the ones I know best. I defer to professor Oschema's book for later usage of the term. First of all, let's get this out of the way: the word Europe, Europa in Latin, is, first and foremost a geographical term. Better still, it is a cosmographical descriptor, meaning that, on a world-wide scale, it refers to one third of the lands that form the inhabited world (Oikoumene). This concept is one inherited by the Middle Ages from Antiquity. Let us refer to a significant text to explain this point.

The Histories against the Pagans, by Paulus Orosius, a contemporary and a collaborator of st. Augustine, was widely read in the Early Middle Ages (reference will be to the page numbers of the 1882 CSEL edition by Zangemeister, which is freely available online) This popular history book begins with a geography lesson. Paulus states that the ancients (maiores) had established that the Earth is divided into three parts, Asia, Europa and Africa. He proceeds to explain the extent of their borders: Europe extends to the west of the river Tanai (the Don), the Meotic marshes (the sea of Azov) and the Pontus Euxinum (the Black Sea), with Constantinopolis presiding over the European sides of the straits. The ocean marks the Western borders and the Strait of Gibraltar (Herculis columnas) receives a special mention [Zangemeister, 9-10]. Further on Paulus gets very specific enumerating the regions within Europe and their respective borders [Zangemeister, 21-28]. To answer your question, yes, the Balkans and Greece (Moesia, Thracia, Macedonia, Achaia and Dalmatia, with Pannonia further north) are indeed part of Europe. This tally of the regions of Europe is nothing out of the norm. That this is primarily a geographical survey and not, for example, an overview of political boundaries that superimposes the concept of Europe to the limits of the Roman Empire, can be seen in the fact that Paulus includes in his list regions, such as Ireland which were never part of the Empire to begin with.

Contemporary authors worked within the same geographical framework and it will remain conceptually unaltered throughout most of the Middle Ages. It would be unconceivable, for example that after the Islamic conquest of Spain and Sicily, these regions would be removed from any survey similar to that of Paulus. The context in which the word Europa appears is primarily one of geography or cosmology. It is true however that different authors at different times use the word with the clear intention of giving it a certain connotation, sometimes religious, sometimes political, sometimes just sentimental. Here is where it gets tricky. These connotations may resemble one another, sometimes they might even resemble concepts that more recent times have attached to the word Europe. The progressive cumulations of these various connotations, or additional, implicit meanings, would eventually coalesce into a notion of Europe that is clearly recognizable to a modern audience. However, it is important to remeber that there is no one-on one correlation between the historical notions of Europe found in each individual medieval text and the present-day perspective, which has been marked by more recent ideas and events (especially in the 20th century) which were completely alien to the medieval world.