South Africa would work as a substitute or in addition to America for the Puritans. What it would take literally would be a British East India Company ship getting shipwrecked with seeds for vegetables and or grain so that the crew could subsist on it for a year until the next ship came by. Because until Jan van Riebeck's ship got shipwrecked at Table Bay, Europeans thought the Cape was inhospitable for farming because it had no trees; just fymbos scrub. It literally took a ship getting wrecked on the Cape (and it was bound to happen sometime; it just took until 1652, it could easily have been butterflied ahead to a British ship in 1610) to convince Europeans that yes, Europeans could grow crops there. Once that happened, the BEIC would be just as much in the market for Dissenter colonies wanting to put down roots in land they had been granted by Queen Elizabeth as the Plymouth and London Company were. And some would have taken them up on it. So a Puritan settlement on the Cape is by no means fanciful.
As for a Hugenot settlement in the 16th Century, Australia would have been the safest place on earth to plant such a settlement. Because at that time, Hugenots were pariahs and outlaws. The French Crown would not protect them since they were not Catholic. They were fair game for the Spanish and Portuguese who wanted to burn their settlements and kill them. And burn their settlements the Spanish and Portuguese did, as soon as they found them. The Spanish at Port Royale in South Carolina and the Portuguese at Guamabara Bay. Even if the Hugenots had settled farther south, say at Bahia Blanca or the Rio Negro, the Spanish would have eventually found them---or on the Cape Coast. So if Coligny had sent an exploration party due east from the Cape of Good Hope to look for Terrra Australis and found Australia, a settlement on Australia, even on the West Coast, but better yet on the East Coast in what is now Tasmania, Victoria or New South Wales might well have remained undiscovered by other Europeans long enough to grow large enough and strong enough to where an expeditionary force by a Catholic power could not root them out. However long--50 years, 100 years, it might take.