In 1716 the records would have been in the parishes. There have also been many changes since then. You will probably have to find the parishes in the area he was in. I am from Charleston and there were a lot of them. You may need to look at old maps in that time period.
There was also a family of McKee that came to Charleston from Ireland in 1772. I did find it noted that the surname was sometimes incorrectly spelled McGee so, you may want to try searching that spelling too. The incorrect spelling of names was common back then.
Here are some links, hope they can help.
South Carolina GenWeb There were only 4 counties in SC in 1710 1710 Counties Map and the SC Churches and Genealogy Charleston Church Records.
We lost a lot of old records during the US Civil War too.