While not overly popular in NC at the time, Edwards did have some national popularity and gave Kerry some problems in the primary. Plus, Kerry needed someone to balance out the "MA liberal" label and figured Edwards was a good choice from down south.
The irony is, Edwards made some comments after the election that Kerry ran a very poor "map" campaign and allowed Bush way too much offensive time on the map, attacking Kerry in bluish states (MN, MI, PA, etc) rather than battling Bush in his tight states. In addition, Edwards was also pissed (as was Mark Warner) that Kerry gave up in VA, which was winnable for the democrats in 2004.
I'm not sure the Kerry campaign could have done a worse job in VA and WV in 2004. They were both there for him, and the WAY which he showed his political incompetence was a huge factor in the MOV for Bush in both states.