Starnes graduated from Glendale High in 2007. He was the starting quarterback during his junior and senior years. In his senior season, he led the Falcons to a district title and a state semifinal playoff berth. He earned honors, including All Ozarks Conference, All District Class 5A, 2007 Grin-Iron All-Star Game Offensive MVP, 2006-2007 Springfield, Missouri High School Player of the Year, 2007 Max Emfinger All-American, and 2006 Elite 11 Regional QB. He was awarded the Bill Wainwright Player of the Year Award his senior year for leading the Ozark Conference in rushing, scoring and total offense. Also while in high school, he was also a member of the track & field team and the golf team.
Starnes played football for head coach Terry Allen at Missouri State University in Springfield. He joined Allen's first recruiting class as part of the team in fall 2006. In Starne's first season at Missouri State, the decision was made to move from quarterback to wide receiver. As a result, he redshirted the 2007 season. The 2008 season was Starnes' first year of eligibility. In his senior season, Starnes was named the Coors Light Media Player of the week for his performance against North Dakota State, the eventual FCS national champions. Starnes was also recognized in 2011 & 2012 for his academic success alongside other student-athletes.