Fatal error on cart REST API calls: Cannot instantiate interface Magento\Framework\MessageQueue\ConfigInterface

The solution was to force a re-install of the 2.3.1 upgrade. Muhammad's answer was on the right track, but I had to take some extra steps because his instructions are only for people who had problems during the upgrade process - which I didn't. I discovered these problems a while after I had upgraded to 2.3.1.

Anyway, first of all I reinstalled the Magento Base module by editing vendor/composer/installed.json and renaming magento/magento2-base to __magento/magento2-base (basically making Composer think the module is not installed as per this comment) and running composer install.

Then I downloaded Magento's command line upgrade script and followed the instructions from that page very carefully.

It seems to have worked - I assume the problem was that one of Magento's base modules hadn't installed or updated correctly because I didn't follow Magento's recommended upgrade procedures as carefully as I should have. Forcing a reinstall of the base modules and re-running the upgrade correctly seems to reset everything to working.

If that hadn't worked my next alternative was probably going to be to delete everything inside the vendor directory, and run composer install again - essentially forcing all dependencies to reinstall from scratch.