If Alexander was Greek, why was he famous as Macedonian Alexander?

Because to the Greeks, the people who spoke about him the most, and whose historical accounts influenced the West’s understanding of Alexander the most, saying he was Greek wouldn’t mean anything: they were Greek themselves, after all. But saying he was from Macedon meant a lot to Greeks: Macedon had a marginal presence in Classical antiquity, then all of a sudden conquered the world. (That’s not taking a side on how Greek the Ancient Macedonians were, btw.) And Macedon was the state he was the king of, not Greece.

If you want some parallels, try George W Bush: to Americans, and indeed to the Anglosphere, the fact that he was (or rather, proclaimed himself to be) Texan was noteworthy; the fact that he was American was taken as given. And Franz-Joseph was the emperor of Austria–Hungary; we don’t refer to him as Austrian.

I was hoping to find instances of the people he conquered calling him Alexander the Greek, but it doesn’t look like it. Hebrew per Wikipedia (אלכסנדר הגדול – ויקיפדיה) uses Alexander the Great אלכסנדר הגדול or Alexander of Macedon אלכסנדר מוקדון. Ditto Arabic per Wikipedia (الإسكندر الأكبر – ويكيبيديا، الموسوعة الحرة): Alexander the Great (الإسكندر الأكبر، والإسكندر الكبير) or Alexander of Macedon (الإسكندر المقدوني), or Alexander the Two-Horned (الإسكندر ذو القرنين)—though per Alexander the Great in the Quran – Wikipedia, the earliest identification of the Two-Horned One of the Quran with Alexander, in the 9th century, referred to him as Greek:

Dhu al-Qarnain is Alexander the Greek, the king of Persia and Greece, or the king of the east and the west, for because of this he was called Dhul-Qarnayn [meaning, ‘the two-horned one’]