I would not miss Maurice's in Columbia. They are not all the same. Some just reheat the food. I think my favorite that I tried was on Devine St.
Looks like you'll be missing Lexington BBQ, which would be one of my other recommendations. Going north from Fayetteville, I would hit the original Q Shack in Durham. It is Texas style BBQ (not local). They have good ribs and brisket. Their cobb salad is excellent if you're into that sort of thing. Best side is their spinach in my opinion, but others like the okra and mac and cheese. Only go to the Original Q Shack on University:
http://www.theqshackoriginal.com/
In Richmond, I enjoy Q BBQ. I like the ribs, pulled pork and chicken. The brisket usually is not so good. Pineapple hot dish is one that people love or hate. I love it. It's very sweet.
https://qbarbeque.com/
There isn't a whole lot in Sharpsburg. A couple times we stayed at a B&B that is a farm and was around during the Civil War. The ladies who ran the place had some great stories, especially about the armies waiting it out on their farm after the battle ended. We enjoyed it enough to go back a second time:
https://elmwoodfarmbandb.com/about-the-farm/
Ate BBQ that was cooked in a parking lot one afternoon just near the center of town and it was pretty good.
We had an excellent meal at 28 South in Hagerstown, which isn't too far away.
http://28south.net/
At Gettysburg we always stay at Swope Manor. Again, a B&B. Breakfast is one of the best we've had at any B&B. The house was around during the war and the hostess dresses in period outfits and is a wealth of information. We could listen to her for hours just talking about the history of the house. Yes, and she also knows a lot about other things also. They have special events for holidays, dinners and such. The house is beautiful and this time of year, it is virtually empty. They have a library, bake cookies for you in the afternoon, coffee, tea, etc. It's really lovely place to stay.
http://theswopemanor.com/
For food, we love Food 101 (it's about two blocks from the center, a 10 minute walk from Swope Manor). There also is an Irish Pub across the street that is good for drinks and dinner. Dobbin House Tavern was good, but not as memorable as the other two, although the building is beautiful.
There are a number of other restaurants in town (especially right on the main square), but they seemed a bit more generic.
There wasn't a whole lot in the way of BBQ in that area. We have stopped at 3Hogs BBQ in Hanover. Liked the BBQ eggrolls. The food is twisted. You can check out some of the pictures and see what you think.
https://www.facebook.com/3hogsbbq/