The more I look at this, the more I think that Phoebe's parents are indeed Francis Hodge and Nancy Walker. At the time that they were reportedly married, Belfast was in Bedford County, and it appears that Francis Hodge may have been down in this area. Unfortunately, Bedford County records have all been destroyed at various times in the past, so it is difficult to say. Francis and Nancy did have a daughter named Phoebe - or so family records say - but it is unknown what eventually happened to her. Given that Seldon and Phoebe named two of their children Francis and Nancy, it seems very possible - even probable - that this is the link.
As Marshall County was not formed until 1836, and Bedford County records appear to have been destroyed, I was wondering what your source is for the very specific marriage date - I would assuume a family bible or some such.
What puzzles me though is that Francis and Nancy left Tennessee around 1830 for McLean County, Illinois to be with their son William Herron Hodge, and daughter Mary Baker. She would have been a bit young to remain, unless she stayed with a brother or sister - such as possibly Nancy Wortham.