Here's where all the magic (sense 2b) begins: with magic.
The word magic goes back to the 1300s, and it originally referred to rituals, incantations, or actions thought to have supernatural power over the natural world. This is the sort of magic that shows up in the Harry Potter series, and the kind that the people accused of witchcraft in 17th-century Massachusetts were accused of performing. By the 1700s, magic had also come to refer to anything that seemed like a supernatural power
...there's magic in thy majesty!
— William Shakespeare, A Winter's Tale, 1616
and by the 1800s, magic was also applied to the tricks and sleights of hand that conjurers and magicians did.
But the word has its origins in something that's not necessarily magical in any modern sense. The word comes from an ancient Iranian word, borrowed into Greek, that gave us the names of the Magi.
For those not up on their Christmas lore, the Magi are three men, sometimes reckoned as kings, priests, or astrologers, who traveled from their homes east of Israel upon reading a portent in the sky (a star) in order to pay homage to the infant Jesus. The name Magi was also given to a hereditary class of Zoroastrian priests of the ancient Medes or Persians—though this use of the word Magi in English comes several hundred years after the name given to the traditional "Three Wise Men." (Magi is plural: magus is the singular.)
The root from which both magus and magic stem refers to a sorcerer. The Old Persian magûs also gave us a word familiar to gamers: mage.