Hook into \Mage_Checkout_CartController::estimatePostAction and set the countryId() in the billing address to the specified country.
/**
* Use the country from the shipping estimator in the checkout
*
* @event controller_action_predispatch_checkout_cart_estimatePost
* @param Varien_Event_Observer $observer
*/
public function controllerActionPredispatchCheckoutCartEstimatePost(Varien_Event_Observer $observer)
{
$request = $observer->getControllerAction()->getRequest();
$country = (string) $request->getParam('country_id');
$cart = Mage::getSingleton('checkout/cart');
$cart->getQuote()->getBillingAddress()->setCountryId($country);
}