Hi Ryan,
You create and name the statuses yourself, so there could be no existing translations, as there would be no way to know what you would call your statuses. And, when you create a status, it’s stored in your WordPress database, not the plugin files, so, naturally, it would not be found in the plugin strings.
That being said, you would have two options to accomplish this:
1) You could create a separate set of statuses for each translation. For example: translate “pending payment, processing, on-hole, complete, etc.” in Language A, and “pending payment, processing, on-hole, complete, etc.” in Language B. That way, for orders that are in one language, you can use the statuses that you’ve created for that language, and then use the separate set for the other language.
2) Translation plugins like WPML often have a feature to translate database entries. For example, WPML’s String Translation add-on lets you translate entries from the wp_options table, etc. Since our statuses are stored in the database, if you have a translation plugin that allows you to translate database entries, you should be able to find and translate them there.