Tennessee seems more plausible, but Mississippi would be more interesting.
I picked Mississippi because he was born there. Maybe he could come home to Mississippi in '67 for a run at the governorship, rather than a renewed political career? It's possible he could've won the crowded Democratic primary that year using name recognition, beating out John Bell Williams and Ross Barnett, among others; alternatively, he could've most likely won the GOP nomination with ease, though that would make the election rather more difficult.
Maybe have John Stennis die in 1973? Elvis might have had a better shot running in '73 than in '67, and in a special election rather than a gubernatorial election.
Regardless, he would've been anti-segregationist - Elvis Presley, contrary to the myth that he wanted African-Americans to "buy my records and shine my shoes" (which he never actually said), was not a racist by any means.