I don’t know how you count border states, but this guy was elected to the Kentucky Legislature in the 1930s. West Virginia might have had a few African-American legislators earlier, as it seems like that state never really tried to suppress the vote to any great extent.
I don’t know if any got elected in the old Confederacy pre-1960s (post Reconstruction), but I’m not completely sure about Tennessee, since African-Americans had long been able to vote fairly easily in such cities as Memphis.
Charles W. Anderson Jr. (R-KY) was in fact the first to be elected to a Southern state legislature since Reconstruction. Who was the first to be elected mayor of a Southern city since Reconstruction?