You are right about his name. It is Tohei.
I checked it in Kobayashi Sensei's biography in English:
As you guessed right,
The kanji "To" can be read "Fuji" meaning wisteria.
"Hei" can be read "Hira" meaning even, flat or level.
As a family name, I think Fuji-hira sounds natural, though.
Because he taught Aikido in Hawaii and America, he may have thought that To-hei was easier to pronounce. I am not quite sure. We will have a dojo-cho keiko (practice with the head master) at our dojo on August 25th followed by a party, so I will ask Kobayashi Sensei about this.
As to the sho-dan/sho-kyu (sho=promotion) test, a shodan(sho=beginning dan=1st dan) holder can challenge nidan in two years. I will try nidan (second dan) in probably three years or more.