Nice! I have done a similar trip 5 years ago.
From Fethiye to Nevşehir is at least 13 hours by bus. If there are direct busses they are not very frequent. Anyway, it makes sense to split the trip!
We went from Nevşehir to Fethiye via Konya and Antalya. To give you an order of magnitude of the legs:
- Fethiye - Antalya: 3 hours
- Antalya - Konya: 6 hours
- Konya - Nevşehir: 4 hours
You can of course only make one stop in Konya or Antalya. That's up to you. You should also be aware of the fact that there are two routes from Fethiye to Antalya. One along the coast and one inside the country. The latter is much faster! Along the coast takes 6 to 7 hours. It is a scenic but very shaky route.
I had to plan the stop in Antalya as part of a compromise with my better half. I would have preferred to stop over in Konya and Eğirdir, rather than Anatalya. But that's life ;-) Eğirdir is really a nice place. Everybody who has been there seems to like it.
If ever you are in a hurry, and you only want to see Fethiye, Cappadocia and Istanbul, without stopovers, I would do it it the following order: Fethiye - Istanbul - Nevshehir. From the point of view of bus transport it is easier to plan and to handle. This being said, there are also interesting stopovers along the latter journey!
The coaches to the Cappadocian villages transit through Nevşehir. From there you will be transferred to whatever your final destination in Cappadocia. That's why I am talking about Nevşehir.
If you have trouble to find a direct bus to Nevşehir you can also try to find a bus to Kayseri or Aksaray, as a plan B. These cities are really nearby and you have frequent buses to the Cappadocian villages (via Nevşehir).
Although I think that Pamukkale has a limited interest, the two options you have added make sense too. Now you have to play and pick the "best" option.