You get this problem if you remove an extension manually, or the extension doesn’t clean up properly behind itself (which most don’t).
To remedy in phpmyadmin do the following:
delete FROM `core_config_data` WHERE path like “carriers/<shipping_name>%”
replacing <shipping_name> with the error name you have received e.g.
delete FROM `core_config_data` WHERE path like “carriers/freeoptionalshipping%”
Suggest you make sure you understand what you are doing before running commands like this, and take a backup of your db if in any doubt, as it could screw up your db if you do it wrong!!