What route did the First Virginian take, when entering the state?
No one alive today knows who was the first person to step into Virginia - and when that happened thousands of years ago, the first Virginian would have had no concept of "Virginia" or the United States. I assume that the first Virginian was a hunter on an extended journey, following a river valley upstream from what today we call the Ohio or Tennessee River, or traveling downstream along the shoreline of what we now call the Potomac River.
Take a look again at Virginia hydrography. The main drainages, where Paleo-Indian hunters walking upstream might have entered the state from the north, south, or west, are now known as the Potomac, New, Powell, Clinch, and Holston rivers. (The last three are tributaries of the Tennessee River... but you knew that, right?)
Perhaps that first Virginian followed a deer trail up what we now call the Russell Fork River, and crossed through what is now Breaks Interstate Park on the Kentucky-Virginia border into Dickinson County. It is possible someone walked up a side valley from the Kanawha or Potomac rivers and crossed the watershed divide into the James River watershed.
However, the first human in Virginia could have come via the coast rather than by following a river upstream. He (or she) may have walked down the northern coast at the edge of the Atlantic Ocean, ventured southward along the beach, and crossed over into modern Accomack County on the Eastern Shore. Or the first Virginian might have come northward from the warmer south, walking upstream from today's North Carolina by following the coastline to the modern False Cape State Park or the lands on the western shore of Back Bay. If the "Green Sea" swampland between the Back Bay and the Dismal Swamp had been too difficult, or too barren of game suitable for hunting, perhaps they walked inland and followed the Roanoke, Meherrin, or Nottaway rivers upstream.
Roanoke, Meherrin, and Nottaway are Native American names for those rivers - but do you think those were the original names adopted eons ago, or just the names used by the residents in the early 1600's when the Europeans arrived? What today we call the James River was called the Powhatan River before the English arrived. The English changed the name to honor their ruler, but the odds are very good that the Native Americans under Powhatan's control had done the same thing within the last 30 years. The first Virginians, maybe 15-25,000 years ago, did not speak the Algonquian language or have a chief called Powhatan... so the original names of the Virginia rivers were not the names recorded by John Smith on his map of Virginia.