Quite famously, during his own lifetime, Alexander claimed some kind of "divine descent". He made an out-of-the-way journey to a famous religious site in the Libyan desert, to underline this.

Some would have believed him. Others, wouldn't.

The mere fact that he used to fight in the frontline of every battle, and still walked away (the only other military leader who can match him in this was Khalid bin Walid) - that would tend to sway opinion on the "wow, he's indestructible" debate.

When news of his death reached Greece, people stalled celebrating, as he was not really considered "merely human".

(Remember, Alexander was still recognized as Macedonian, not Greek - and in fact 50,000 Greek hoplites went with Memnon of Rhodes to fight for Iran against Alexander - which they did till the end. It's only much much later that Greek society appropriated him as one of their own. In fact, historical accounts showed that Alexander himself tired of aspiring to be Greek, and took on many trappings of the Iranian court & system, till his end)