You've done a good job narrowing down the window in which your ancestor came to the US -- for some tips to other records that might give clues, see Tracing US ancestor back to Germany?
Why the National Archives Can't Help
The difficulty for this case is that the US Federal Government did not require the masters of ships to turn in passenger lists until 1820, so any passenger lists which survive will not be at the US National Archives (NARA). NARA's article Immigration Records gives a brief list of reference works you could use to get started in Part 2: 1538-1819, under the heading What we don't have.
Entering the names of those books in WorldCat.org will show you the listing in WorldCat's catalog, and by entering your location into WorldCat's locator, you can find out which libraries near you have the books in their collections.
Online and Off-line Resources
Joe Beine's site German Roots has a great deal of information about tracing your German ancestors' journeys to the US. His guide Finding Passenger Lists Before 1820 helps sort out what has been published in book form, what has been made available on CD-ROM, and what might be online.
At the time I write this, the online databases listed online for Georgia and the Carolinas are before 1805, but it's worthwhile to keep an eye on this page to see if other sites are added to this guide.
Beine's guide Finding Passenger Arrival Lists & Immigration Records for Charleston & South Carolina has a breakdown of the Early South Carolina Settlers CD-ROM, which has several data collections that could be of use in answering questions about your family. More information about this set of CD-ROMs is available from the website of Genealogical.com, and in the FamilySearch Catalog; find copies in a library near you by using WorldCat
Another good site for immigration research is Olive Tree Genealogy. The page Ships Passenger Lists to South Carolina includes some of the material found on the German Roots site, plus some transcriptions of individual passenger lists. Also see her North Carolina page.
Publications
Another way to get information is to look for case studies from other people studying the same time and place. Look for bloggers who have written about your areas of interest, or about migration patterns that include your area of interest. For print publications, the Allen County Public Library's Periodical Source Index (PERSI) can be searched with a subscription at Find My Past -- an older version is available via HeritageQuest, which you may be able to access at a local library. If you find a reference to an article that interests you, you can order a copy of the article. PERSI is also a good resource just to find out what genealogical periodicals exist for your geographical areas of interest.
Other avenues of research
If you have your ancestor's 1870 Census record, there is a column to the far right which is supposed to be ticked when the person is a US Citizen. NARA's guide Clues to Census Records, 1850-1940 says:
The 1870 census (column 19) has a check mark for "Male Citizens of the U.S. of 21 years of age and upwards." If the person was a foreign-born citizen, this means that he had become naturalized by 1870.
You may not be able to find a Naturalization record for him, or if you do, it may not have any helpful information in it. The Family History Library presented a class last year which is not yet online, but you can download the handout: “Why didn’t my Ancestor Naturalize?”: Navigating U.S. Naturalization Records by Danielle Batson, AG.
In the section 1790 to 1906 Time Period, Batson describes the Naturalization process and the nature of the pre-1906 Naturalization records. Naturalizations were done at the local (county court) level, and there were no standardized forms, so the information varies. Batson says:
The content of naturalization records in this time period might
include the port of arrival, date of immigration, country of origin,
and age of the applicant. Forms were not standardized in this time
period and each court used their own forms. Thus, information varied
widely.
Immigrants generally naturalized in county courts near their homes. Be aware that not all naturalizations can be found in court records that are neatly labeled as such. Sometimes the events are noted in the ordinary county court minute books that list all the doings of the court for that day.
If you can find a reference to your ancestor's arrival in a record like this which has a search name, you may be able to learn more by researching the ship itself.
If you can't find your ancestor, you can also try searching for records of siblings, other family members, his associates, and his neighbors, to see if you can find their arrival records.
