Here are a couple of Paine/Payne and Walls connections. Keep in mind that a surname could be spelled differently in one document to the other. All genealogists know this, so do not ever disregard a surname that is spelled differently without checking it out. Many of the people who handled the source documents had little education, or were not good spelling. Furthermore, some of the people were hard for other people to understand, so they wrote down whatever it sounded like.
Benjamin Franklin Paine was born 6 Sept 1830, Big Creek, Monroe County, TN and died 28 July 1900 (dates per pension claim), buried Old Coker Creek (Station) Cemetery, Monroe County, TN. Son of John C. Payne, Jr. and Jane (Walls) Payne of Monroe County TN, and grandson of John C. Payne, Sr. Married (1) 1855 Cherokee County, NC to Jane Bryson, born 7 Feb 1865. Jane Bryson, sister of Captain Goldman Bryson daughter of John and Margaret Bryson. Married (2) 29 March 1868, Madisonville, TN to Jane Kirkpatrick. *I believe the source is "Hill Country Heritage" by Paul J. Long (Robert Barker files).
My guess is that if you find the above person you will find others you are looking for by searching those they are connected to. Coker Creek, Mouse Creek, and Persimmon Creek are all family haunts of our families. I do not have this source information, so it looks like you will have to confirm it on your own. Good luck.