Debatable. A few butterflies after Alexander can prevent the birth of thousands of kings. Extreme example: Montezuma's Great-Great-Great...-Great-Great Grandfather is struck by lightning from a new thunderstorm, and dies. Extreme Result: Tarascan Iron-Wielding Empire. Moderate Example: Rainy day. Cortes's expedition doesn't set sail, and another Spaniard lands the next year in Mexico. The stars aren't lined up, the Aztecs don't accept him as Quetzalcoatl, and he dies.
Regarding OP:
1. Why would Alexander lose control of Egypt and Israel? He particularly valued Egypt, as it was where he learned from an oracle that he is the son of Zeus, and he wouldn't be pleased that the Jews refuse to sacrifice in his name. If anything, he'd bring down fire and sword on the Egyptians and Israelites if they try anything. And then he'll conquer Arabia and Sicily (his OTL plan anyway).
2. The Punic Wars honed the Roman Army into a force to be reckoned with, and the presence of another major Mediterranean power makes conquest elsewhere more difficult. Besides, a strong Alexandrian Empire closes off Greece and Illyria (sure to fall into Alexandrian territory) to them. Gaul is the only place they can expand into, but I don't think the Carthaginians would be happy with the Romans becoming so powerful without a good counterweight. In this scenario, Rome is confined to Italy, and Carthage colonizes Spain, North Africa, and Morocco. Unless Alexander conquers them (and the Romans), as he had plans to.
3. Possible. Merchant states of Alexandrian Arabia might be interested in trade with the Africans, who trade ivory and gold for weapons and a general flow of ideas. But not likely. An Alexandrian Empire controlling Persia and Bactria would mean safe land trade to India and China, so the OTL incentive to develop good maritime trade (what led Europe to Africa) doesn't exist for a while, and the lack of Islam (and its missionary culture) prevents the meeting of the Eurasian and African cultures. If anything, Africa is less developed ITTL, unless the Bantu peoples develop an Iron-age civilization on their own.
4. And how will they hold this empire together, or even start it? The Incas, admittedly, did something similar in the Andes, but they had a little something called organized bureaucracy and agriculture. The Apaches and Comanches had neither. They were hunter-gatherers, with little incentive to start farming. Farming leads to Empire, and without farming, no empire of any size can exist.
5. Why would they do that? They did pretty well at holding it together IOTL, as nomads. They could have ruled everything from China to the Rhine, if not for their rather sedentary custom of having to return to Mongolia to elect a new Khan (this stopped them at Vienna). If anything, the best thing to do to the Mongols is to make them more nomadic.
6. The Maori? Sure, they had great canoes, but that alone is insufficient for building an Empire. If they develop bronze-working, I can see them conquering Eastern Australia and parts of Polynesia, but no more. Besides, why would they "Join forces" with the Australian Aboriginals? The latter were hunter-gatherers, the least developed (technologically and bureaucratically) people on earth. Why would the Maori, notoriously violent, bother joining forces with them when they can slaughter whole tribes with a dozen warriors and just outright conquer and enslave them?
7. Why? The Aztecs were certainly up to the task of building Mediterranean-level ships by 1500. They were certainly up to the task of making tar, and glue, and even some degree of nails. This would be sufficient for ships like those of the ancient Greeks and Egyptians. But they didn't, because there was nothing there to get. The Europeans went out for plunder, for resources, for land, and from a divinely-ordained mission of converting the natives. The Aztecs had to gain, at most, some sacrifice victims (there was nothing in the Caribbean or Yucatan or coastal USA that they didn't have within their own territory), but why go so far to obtain them?