The main reason this type of claim is made is because of the impact of Alexander the Great (AtG from now on) had on the eastern mediterranean and ANE. Essentially, he ushered in the Hellenistic period, and spread Hellenic language, and so Greek culture, throughout that area. Egypt, Palestine and the coastal area, Asia Minor, and extending into what we think of as Iran/Iraq/parts of Saudia Arabia, all became Greek speaking and adopted and adapted Hellenic cultural patterns and ideals to varying degrees.

This created a certain level of homogeneity, which persisted long after AtG was off the scene. Indeed, even as the eastern mediterranean was incorporated piece by piece into the Roman empire, it was still almost entirely Greek speaking, so that the Roman Empire had a linguistic divide right down its centre (roughly the Balkans). The conquest of the Greek eastern-mediterranean had its own influence on Rome, namely the importation and adaptation of Greek language and Greek culture to Rome and especially Roman elites.

How did this pave the way for Christianity? Christianity only had to make one major linguistic and cultural 'jump' in order to access most of the expansive Roman Empire at a period of fairly extensive control. Once Christianity shifted to Greek-language content, which it obviously did extremely early since its canonical New Testament is entirely composed in Koine, it had access to all those regions, and it mainly had to speak to a cultural spread all influenced by Hellenic ideas. Of course, Christianity did make the leap to other languages and cultures, indeed I would argue that the missionary impulse in early Christianity led it to do so, but Greek provided the easiest, most readily available 'linguistic vehicle', which opened up the most people (since the Eastern mediterranean was also more heavily populated than the western half of the Roman Empire.

That's probably what Iron Maiden mean in their song, it's certainly what people who think of AtG's influence on later Christianity mean.