I would try searching using the names ideally of one or two of the male children with the least common names.
Male children are better as they dont tend to change names, and being younger than their father they hopefully lived long enough to generate more of a paper trail. I'm afraid you may find the family almost anywhere, by the 1880s although many people lived their whole life in the same area, many others would migrate long distances travelling the states by railroad, horse and boat for a variety of reasons.
Depending on what names you have there may be a lot of false leads to eliminate but you can soon whittle down possibles.
I would also consider posting a bit more info on your great grandfathers family on message boards here and on other sites. Often a fresh pair of eyes works wonders.
I had a look at the name you gave in
Cherokee County, NC and straight away found 2 families. Not knowing which waqs your grandfather straight away made it harder.
Neil.