I don’t know of a plugin that does it in a general way; for the most part, you’ll need to build something custom for each specific API you intend to communicate with.
For your purposes, the key function will be wp_remote_post(), which is a wrapper for the POST method of WP’s HTTP class. (Use this instead of making manual cURL requests, because WP_Http has all kinds of fallbacks for different modes of HTTP transport.) Here’s a nice introduction: http://yoast.com/wp-best-practice/wordpress-http-api/ Same origin policies generally only apply to browsers. wp_remote_post() and its ilk are fired on the server.
Sending data is pretty easy – just put an array into the ‘body’ of your wp_remote_post() call. The tricky part is always authentication – does the API server expect a pre-registered key, or some sort of oAuth handoff, or what. If it’s as simple as a shared key, you can just pass it as part of the 'body' payload.