1) Run the Intersect (Analysis) tool http://resources.arcgis.com/en/help/main/10.1/index.html#//00080000000p000000
2) Add your states polygon layer as the only input feature
3) Specify your output shapefile
4) Change your Output Type to LINE
The output layer will show all the lines shared by all the polygons in your input layer. Note that you will have two lines per adjacent border. Select one of the lines (border between GA and NC for example) and export it to a shapefile. Use this shapefile in your Near (Analysis) tool.
----- or -----
1) Select Georgia, export it out as a shapefile, call it GA
2) Select North Carolina, export it out as a shapefile, call it NC
3) Run Intersect (Analysis), use GA and NC as inputs, specify your output shapefile, change your output layer type to LINE
The output line layer will show exactly where the two polygons share boundaries.
Repeat for other states as necessary.