To what extent did BC gentiles have access to the Old Testament? In Matthew 2:5-6 we see the wise men from the East telling Herod of the king who was to be born in Bethlehem, and they seem to be quoting from Micah 5:2. 

Did gentiles have access to the Old Testament before Christ? Could they have known what Micah said without having the book of Micah?
During the Jewish exile in Babylon, Daniel (Belteshazzar) was appointed as the "chief of the magicians" (Daniel 2:48; 4:9). This was probably the same group as the magi (source). During Daniel's time in Babylon, he interpreted many dreams both for the king and for himself. One such vision foretold the year of the crucifixion of the Messiah, or "Anointed One".

In Daniel 9:24-27, he is told of a period of 70 weeks (which are understood to be weeks of years) that are fixed for the Jewish people. There are seven weeks, then sixty-two weeks, with the final week being a subject of controversy among Christians. However, the first sixty-nine weeks point to the year of Jesus' crucifixion.

The magi were no doubt familiar with Daniel's prophecies since he was such an important figure in Babylon and Persia during Judah's seventy-year exile. Thus they likely were expecting something to occur in their lifetimes.

Regarding the star, the magi might have been looking for it because of the prophecy of Balaam, the sinful prophet in Numbers 24. In verse 17, he said, "A star shall come forth from Jacob, a scepter shall rise from Israel." Some have speculated that Balaam was an early magi since he lived in the general vicinity of Persia, so the magi might have known about this prophecy through him.