I'd like to mention another possible candidate for this honor, one João Bermudes, who could have accomplished this feat depending on how one defines "circumnavigate Africa", but he clearly made his way around this continent at least once, if not twice.
Bermudes is one of these sketchy characters whom one encounters in history: a person of no great abilities, nevertheless manages to find a golden opportunity which he uses to hustles his way into power & prestige, only to be revealed to be a fraud & cast out. He was a minor member of the first Portuguese embassy to Ethiopia in 1520, sailing with the ambassador from Portugal to Massawa on the Red Sea coast, by way of India. He is remembered in that group for two things: suffering a serious injury while wrestling one of the native Ethiopians (IIRC, he broke his leg); & as one of two people left behind to learn the language as a benefit for the Portuguese king when the ambassador left to return home. (Or that was a convenient excuse to leave Bermudes behind because he had been such an annoying jerk.)
When the ambassador left, things looked very good for the Ethiopian emperor, Dawit III. However, a few years later a Muslim Imam Ahmad Gragn, led a Jihad against the Christian polity, won several battles & conquered most of Ethiopia. Things were desperate by 1531 & Dawit assigned Bermudes the task to travelling to Europe to ask for help. Since Bermudes was a lone individual with no real standing amongst the Portuguese government, he could not return to India & seek passage back to Europe that way, so he was forced to somehow make his way to the shores of the Mediterranean & seek passage from there. (There is evidence that he was in Rome before he reached Portugal.) So it can be argued at this point Bermudes circumnavigated Africa, although not in one trip, & perhaps not entirely by ship.
Bermudes Ethiopian adventure did not end there. When he appeared in Europe, he claimed to be the Patriarch of the Ethiopian church, having been duly appointed & consecrated by emperor Dawit III. Failing to make much of an impression on the current Pope, beyond receiving some money for his immediate needs & further travel expenses, Bermudes proceeded to Lisbon where he was more warmly received. The idea of a crusade on behalf of the Ethiopians sounded good to some members of the Portuguese court, so he was included in the party of the new Viceroy of Portuguese India, Estêvão da Gama, & arrived in India by 1540. That same year da Gama prepared a naval expedition to attack the Ottoman fleet stationed at Suez, which included Bermudes.
The Portuguese attack on Suez came to naught: da Gama found he had too few ships to successfully attack the Ottoman fleet. Moreover, upon returning to Massawa where he had left a group to secure his rear, he discovered that Bermudes had incited a near-mutiny over the cause of rescuing Christian Ethiopia from the Muslims. Da Gama, seeing this was the easiest course, gave in to the demands of his men. He allowed 400 volunteers under the command of his brother Cristóvão da Gama to land & come to the aid of the local Christians. This Cristóvão succeeded in doing, defeating & killing Imam Ahmad Gragn but at the cost of his own life. And João Bermudes became a central figure in the court of Dawit's son, the Emperor Gelawdewos, claiming he had been appointed & ordained Patriarch of Ethiopia by the Pope.
At this point we have an exchange of letters between governments. One from Gelawdewos to King John of Portugal, asking, in essence, "Who is this João Bermudes fellow? And why does he behave so irresponsibly?" To which John of Portugal replied, in essence, "I dunno. He says your father made him Patriarch. The Pope claims he didn't do it." Shortly afterwards Bermudes found himself exiled to the edge of Ethiopia. He managed to find his way back to the court, only to be exiled a few more times until he found his way aboard a Portuguese ship & made his way back to Portugal. (Technically, he was supposed to receive permission from the Emperor to leave his realm, but by that point the Emperor was content to look the other way & be done of him.)
One could argue that his journey home took him thru Ottoman territories once again, but it is more likely he sailed on a Portuguese ship from India around the Horn. So a second circumnavigation would be unlikely.
Bermudes would likely have been forgotten to history had it not been that he read an account of Cristóvão da Gama's heroic expedition into Ethiopia, decided it made him look bad & wrote his own account of his second sojourn in that land. The translator of Bermudes' memoir, R.S. Whiteway, considers the entire work so much fantasy but having read the translation I find some of the details -- which do not touch on da Gama's actually military expedition -- plausible.