While I have often heard it claimed that the crescent symbol was used by the Byzantine Empire, I haven't seen any examples brought forward, and given the numerous Byzantine coins and other remains we have, someone should have been able to display some example.
However, the crescent and star was a common symbol on the Persian (Sassanid) Empire coins just before the Arab conquest. You can see the crescent and stars quite clearly on sevral of the Khurso II coins, minted a few years before the Arab takeout of the Sassanid empire, which you can see on the following website
Sasanian Empire/Khusro II, page 1
The Persians would have had a lot of interaction with the Turkish tribes of Central Asia, more than the Byzantines, and the Turks could have acquired the crescent symbol from the Persians. As for where the Persian got the symbol, they could have gotten it from older sources, even ones from central asia.