To answer your question, see this previous question for options on changing the country that the Market think your phone is in: How can I circumvent regional restrictions in the Android Market?
For the second part of your question about which country to change to, from the app's description:
Currently for U.S. and Canada based phones only.
But from this description:
- The application dials to our service, which dials to the other party,
showing your phone number as the caller ID.
- The service then records
the call at the telephony level, and sends a very high-quality
recording straight to your email box.
I think that even if you get it to install, it will only work properly if you are currently in the US or Canada, as it seems to work by redirecting your call through a landline call forwarding service, which either won't work in other countries, or will be using a hideously expensive international rate call for that purpose.