In this PR I have done the most minimal version of deprecation, that is, putting a warning in the rcParams validator.

The alternative is deprecating each of the backend's NavigationToolbar classes (there is no superclass to do it in just one place). Based on this information, I agree with your approach of deprecating it for the majority of users (those who don't use pyplot to setup their figures won't necessarily get this message).

Is there an appropriate place to document this change? Perhaps the api_changes document?

The implementation looks good to me. +1

I also agree with the implementation here.

This looks good to me. Deprecating the classes as @pelson suggests would also be fine, but I think the vast majority of users are probably choosing it through the rcParam, which this PR currently addresses.