Kegley gives variants as Starn, Starns, Stern, Sterns, Stearn, and Stearnes. On 26 June 2008 Ancestry.com include 49 entries for Person:Frederick Starnes (1) and wife Mary Goldman; 46 used the Starnes variant, and three used "Starns". There were no Stearns, Sterns variants in use.
Family researchers believe that the "Starnes" surname is a vaiant of the German Palatinate surname "Stering". Members of the Stering family came to America (New York) c. 1710, during the palatinate migration. From there some members of the family using the anglicized "Starnes" surname, moved south into PA, and then VA. Additional work on the equivalency of these surnames is needed.