You didn't mention the time of year, but you seem to be sticking to the south, maybe because it's warmer. The farthest north you get is Matsushima. If you have warm weather, you might venture further north to Lake Towada or into Hokkaido, which has many outdoor places and some interesting cultural stops.
Sado Island is easy to get to, but I've always used a car once there. If you use buses, stop in the info center at Ryotsu Port and get the bus schedules and some maps. I don't remember what info they had if you went into Ogi. There are several car-rental places in Ryotsu. I got a deal on Tocoo.com for the Nissan rental the last time there.
Yakushima is another place to have your own car, although bus service around the island has improved.
You can get good info on Sado and Yakushima as well as other places from the JNTO site
http://www.jnto.go.jp/eng/location/rtg/Most of the places you mentioned were too general to answer a specific question or are covered in a travel book, such as Lonely Planet or Rough Guide and you can find answers there.
What you want to do and see will also determine the direction you go. If you want to drink lots of imported draft beers, head to Fukuoka in Kyushu and look up The Craic and the Porter, a small bar on Oyafuku-dori. If you want outdoor hiking, head to Kirishima in Kagoshima (or north to Hokkaido or south to Yakushima). If you want to soak in hot springs, check out Beppu, Yufuin, Kurokawa, or Ibusuki. If you like old castle walls, Kumamoto-jo is large, Oka-jo in Taketa City is isolated and on a mountaintop, and Obi-jo has good restored buildings as well as original structures. If you want some prehistoric sites, Kyushu also has a lot, such as Yoshinogari, a Yayoi site in northern Kyushu, Jomon-no-mori, a Jomon site on Kagoshima Bay, and Saito-baru kofun, with about 300 burial mounds from the 4th-6th C in Miyazaki. I think the friendliest snack bars are in Yatsushiro and the worst smelling shochu is in Kagoshima. You have a lot of choices and need to narrow them.