that is very similar to what I did!
I did Galisteo-Oliva de Plasencia, the last 8 km are on tarmac, beware
The following morning, you do not have to go back the way you first came or retrace your own steps, you can instead walk ahead through the bull paddocks (beautiful fighting bulls!!!) and end up in Caparra. At the end, you only add 6 km or so to the overall mileage between Carcaboso and Aldeanueva.
It is doable, but beware that from Aldeanueva to Baños it is also 11 km of tarmac at the end of your walking day.
A more sensible approach would be the Hotel Asturias one, but there is something sleepy and easy about Oliva de Plasencia that I really like, just one bar and lazing by the sun, not much to do.
Baños de Montemayor is quite a large place, full of hotels and the like.
From there on, distances are more manageable, indeed, from Fuenterroble de Salvatierra it can be tricky to San PEdro de Rozados, and there are other choices, I will tell you some other time or maybe via private message.
Buen Camino!