Is there any difference between these two?
I shouldn’t have done that.
I shouldn’t have to do that.
Yes. It's the same construction as I shouldn't have answered this vs I shouldn't have to answer this. The latter is a complaint and indicative that not only did I not answer but that I will not answer in the future, while the former indicates that I did answer but now regret it.