Is this possible with the free tools? If so, how? 
the only way to do this is to set up the shipping rules in your paypal account. it's not posible to know the shipping location till they log into paypal, so the shipping rules would need to be configured on the paypal server
If it's not, then I can I achieve this using e-cart with Paypal.
the shipping country is stored in a session variable. you can create different shipping rules based on the shipping country in the session.
You could also use a shipping table for this, but i don't think you really need to, your shipping needs don't seam that complex.
you surely wouldn't need a relational table using the products.
