Hi Caralyn
I don't think anything can be assumed with so little to go on, unfortunately.
A look on the IGI does indicate has high probability of his being English in origin - Sussex also features heavily as a county.
The family may have been English, but who knows how long they might have been in South Africa or how and from where they came to that place.
The father Charles, may have been a seaman (Navy), or Army himself at the time, with his family with him and your man could've been born on a ship in or near Cape of Good Hope at the time. "Innkeeper" does sound "English" though.
Your ancestor - Mr ......... Everest (can we know his first name

)
Do you know how and when he arrived in Australia and from where?
Does his death records have any further information on it regarding parents.
Cheers
AMBLY