Sorry, I’m not a cyclist nor a camping amateur, but I am a resident of Kagoshima city and have had some experiences to go to Nagasaki by car. The most monotonous route (by car) I’ve ever had was to go through coastal route in Saga prefecture (I add, on the contrary, that in Saga prefecture, the northern coastal route was very picturesque). At that time, I went to Hirado island and Ikitsuki island, and come back downwards to Nagasaki city through Sasebo city and western coast line of Nishi-Sonogi peninsula. Great route.
You don’t mention if you use ferryboats or not. I would recommend you to use ferryboat(s) somewhere.
If you don’t use ferryboats, you will have to go up always on the Kyusyu main island not only through Kumamoto prefecture but through Saga prefecture. As I said, this route is a long and a bit monotonous detour, and it’s only a flat, dull, busy with annoying traffic of cars and trucks (except for some coastal part from Kashima to Isahaya). This might be better for cycling, I don’t know.
If you use ferryboats, you have three options:
1. From Kumamoto New port (熊本新港) to Shimabara port, Nagasaki prefecture (島原港、長崎県)
2. Nagasu port (Kumamoto prefecture, 長洲港、熊本県） to Taira port (Shimabara peninsula, Nagasaki prefecture、多比良港、長崎県).
3. The third option I really recommend you and I like best is the route where you use two ferry boats. From Kuranomoto port (Nagashima town, Kagoshima prefecture) to Ushibuka port (Amakusa island, Kumamoto prefecture 牛深港、熊本県). From Ushibuka port, in Shimabara island, you have three options to reach another port, Oniike port (鬼池港) which links with Kuchinotsu port, (Shimabara peninsula 口之津港、島原半島): western coastal route with a great ocean view, central route among mountains and eastern coastal route which is more rural than the two others. Personally, I recommend the third one. Once you reach Kuchinotsu port in Shimabara peninsula, you should go up along the western coastal route (N.50) to Nagasaki city via Obama town which gives you a very nice ocean view and which flat easy route to run by bicicle.
This no.3 option is the route I love personally, but, it’s always by car. I am not sure that my recommendation is suitable for cycling and camping.
As for camping site, I have no idea to give you.