The crescent with a star is one of the oldest astral devices in the record, and every layer of its early history is pre-Islamic.
The earliest well-known instance is Mesopotamian. On a boundary stone of Nebuchadnezzar I, of about the twelfth century BCE, a crescent and a star appear together in the standard divine triad: the crescent of the moon god Sin, the rayed disc of the sun god Shamash, and the star of Ishtar, the planet Venus. These three appear at the head of countless kudurru stones, invoked as guarantors of a land grant. The device is a legal formula as much as a religious one.
It recurs across the Iranian world. From the fifth century CE the star and crescent appears in the marginal decoration of Sasanian coinage and remains in use there for four hundred years, which puts it in continuous circulation across the territory that Islam would later govern.
Independently, a crescent was a civic badge of Byzantium, the Greek city on the Bosphorus, and appears on its coinage from the Hellenistic period, sometimes with an eight-rayed star inside the horns. Later legend attached the crescent to a moonlit night on which the city was saved from a besieger, which is the sort of explanation cities invent for devices whose origins they have forgotten.
None of these traditions is connected to the others by anything but the sky. The crescent and the evening star are simply the two most conspicuous things in it, and it is unsurprising that unrelated cultures drew them together.