Interesting.
Johnson was allowed to run for both offices in 1960; he left the U.S. Senate on January 3, 1961.
William A. Blakley was then appointed to begin Johnson's term, but lost the special election in June 1961 against the 27 years younger Republican opponent John Tower. The question, however, is if the rules have changed in the meantime.
Lloyd Bentsen did the same in 1988, but he only won one race. Joe Biden was also reelected senator in 2008 but stepped down on January 15.
Lieberman was also reelected in 2000, while losing the vice presidency. Not a Senator, but Ron Paul run simultaniously in Republican presidential primary and for reelection in his district. Before LBJ John Nance Garner was reelected Representative the same day he won the vice presidency, but IIRC it was a write-in campaign.