Cheapest way to see Kyushu

I live in Kanazawa and want to go to Kagoshima, Yakushima, Nagasaki and Fukuoka during Spring. I need help with figuring out the cheapest ways to travel between these places as I'm not eligible for a JR Pass.

So far I'm thinking of:
Night bus from Kanazawa to Osaka
Peach flight from Osaka to Kagoshima
Ferry from Kagoshima to Yakushima
Ferry from Yakushima to Kagoshima
Shinkansen from Kagoshima to Nagasaki
Train from Nagasaki to Fukuoka
Flight from Fukuoka to Komatsu (Kanazawa), or
Flighr from Fukuoka to Osaka and night bus back to Kanazawa.

However this will be extremely pricey. Shinkansen seems be the only possible way to travel to and from Kagoshima to other areas in Kyushu. Are there any night buses that travel between Kagoshima to Nagasaki or Fukuoka? Or any other options that would save me money?

Cheers!

It is possible to travel by highway bus (and also by local train, by the way) between any two big cities in Japan. This may require transfers, however, and bus companies' websites are most often in Japanese only. Also, buses on shorter trips do not travel overnight.

Kagoshima-Nagasaki: https://www.keneibus.jp/highway/?rt=kagoshima
Nagasaki-Fukuoka airport: https://www.keneibus.jp/highway/fukuoka/

If you are not able to get a full JR Pass, then presumably you won't be able to get a regional JR Pass either. So, if you don't mind spending more time to get around, there is the Sun-Q bus pass that could save you some money.
http://www.japan-guide.com/e/e2357_014.html
Although some considerable riding is required to make it pay off.
Also there is no shinkansen to Nagasaki. At best you can take the bullet train to Shin-Tosu, and then pick up the ltd express train into Nagasaki City. It is a very interesting places to see though, and worth a couple of days.
https://www.youtube.com/playlist?list=PL7LcPcmoSg-gbw2yXNLK92siHyNqSNx...
You can easily catch a train from Nagasaki to Fukuoka (Hakata Stn) and be there in about 2 hours. While the night life won't rival Osaka, there are some very good sights to see there as well.
http://www.thejapanfaq.com/fukpic.html
https://www.youtube.com/playlist?list=PL7LcPcmoSg-j4RLa6iC7ayvBAbOn8-0...
Finally, it would be a pity if you skipped seeing Sakurajima - it is a rare opportunity to walk around a live volcano while it's puffing away at you.
https://www.youtube.com/playlist?list=PL7LcPcmoSg-irtXXB8IJMdkB9mF0qjn...
There are other great sights in Kumamoto and Beppu.

Thanks for the information! Yes, I'm definitely planning to see Sakurajima. Firas, are you sure there are local trains that go between Kagoshima and Nagasaki? According to Hyperdia the only way to get there via train involves getting a shinkansen for part of the journey. The bus information is really great, thanks for sharing.

One more question: some of my friends who have been to Kagoshima said that the air quality there is really bad due to the volcano. I have sinus issues that tend to get worse from air pollution. How often is the air quality in Kagoshima bad, and does this also apply to Yakushima?

Also do people have to make a booking in advance for the Jetfoil ferry from Kagoshima for Yakushima, or is it okay to buy a ticket on the day?

Firas, are you sure there are local trains that go between Kagoshima and Nagasaki? According to Hyperdia the only way to get there via train involves getting a shinkansen for part of the journey.

Uncheck the "bullet train" and "Nozomi/Mizuho/Hayabusa" boxes to get local train results. Note that it is about a 9-10 hour journey and costs around 10,000 yen.

I hadn't looked it up in detail, but I suppose then it's a no-no, the bus is faster and cheaper (unless you are using the SEishun18).

Oh and about the air in Kagoshima, I also did find it unpleasant, but not unbearable. It also probably depends on wind speed and direction. Wouldn't want to live there, though...