For example, I know the bible isn't to be considered a reliable source and all but there are other examples of this phenomenon. In the bible, Jesus and Pontius Pilate were seemingly able to understand one another. Jesus, the son of a carpenter, doesn't exactly strike me as someone whose education extends much beyond the basic literacy and understanding of the bible strongly implied in the text itself. Likewise, Pilate, the well educated Latin governor of Judea doesn't strike me as someone who would be able to speak the Aramaic of Jesus's native tongue. That signals to me that the exchange was held in Greek. Would it be unusual for non-noble commoners to know Greek to some extent?
The flaw in your premise is asking about Europe, when your question is about Judea.
Pretty much west of the Balkans, Latin was the dominant language of the Roman empire, though Greek was very prevalent among educated Romans and among the upper classes diglossia (switching between two languages to talk about different fields/areas of life) appears common. It's extremely likely that Pontius spoke Greek well.
East of the Balkans , Greek was the dominant lingua franca. Even in areas where another local language was spoken, e.g. Aramaic, Greek was in widespread usage. It was not rven necessarily about formal education, widespread usage of Greek meant that many people were bi or trilingual. For this reason it is not at all unlikely that Jesus knew Greek and could speak in it, even though he was probably not educated in it nor spoke it as well, say, as Pilate.