Android - How to change my device location on the Play Store

(May 2013) I've contacted Google and this is their response:

Thanks for contacting us about country support for Google Play.

We use the billing address of your default payment instrument in Google Wallet to help determine your home country for accessing the Play Store. Our collection of content can vary by country, so your view of the Play Store may differ from what others are seeing when you travel outside of the country listed on your default payment method's billing address.

Please note that you must have a valid payment method with a billing address located inside a country in order to access that country's Play Store.

If you're having issues viewing your intended country's Play Store and would like to change your default payment method or update an existing billing address in Google Wallet, please use the following steps:

1) Sign into your Google Wallet account to manage your payment methods https://wallet.google.com/manage/paymentMethods

2) Add a new card or change your default payment instrument to one with a billing address located inside your desired country

3) Open the Play Store and navigate to any item available for download

4) Click to begin a download until you reach the "Accept and buy" screen (no need to complete the purchase)

5) Close the Play Store and clear data for the Google Play Store application (Settings > Apps > Google Play Store > Clear Data) or clear your browser cache

6) Re-open the Play Store. You should now see the Play Store that matches your default payment instrument's billing country.

If you haven't yet added a payment method to your account for the first time, please add a card directly from the Play Store with a billing address that matches your intended country location. Then, follow steps 3 through 6 to show your intended country's Play Store.

If you believe that you're experiencing a different location-related issue, please first verify if the country of your primary payment method matches your intended country. If the countries match, please provide any screenshots and additional details that might help me resolve your issue.

We appreciate your feedback as we continue bringing more content to Google Play. Thank you for reaching out!

(July 2015) Update

Due to the popularity of this answer, I've decided to add bits to this answer which others have pointed out to improve and update this answer.

• The Accept and buy screen is only available on desktop (not mobile) - thanks @fwuensche
• Google Wallet has changed since the original answer was posted, also try to change your address on these links - thanks @corbacho
• Settings
• Address Book
• Clear all cache and data from the Play Store app
• If you're in a "family account", leave it
• Try these steps of removing and adding back your account - thanks @Dushy
• Google customer support suggests it may take between 30 minutes to 24 hours for the address on the account to refresh.

Tried this answer, but it didn't solve the problem. So I called Google Play support - they did have me clear data from the Play Store app, but also told me to remove my Google account from the Accounts section in settings and add it back. Then they got me to clear the data again from 'Download Manager' and 'Google Play Store' in the apps section and everything worked perfectly after that.

Moved from the UK to Australia and required the banking apps. I had the same problem and tried various things.

What worked for me on a Samsung Galaxy S3:

• Log into Gmail on your PC and change the billing address to the new address (in my case Australian address).

• On the phone, go to Settings, scroll down to Accounts and select Google. Select the account which the phone has been synced with and select Remove account at the bottom.

• Once account has been removed go back to Settings main screen, select Apps, select Google Play Store, tap Force stop, confirm, then tap Clear data and tap Clear Cache.

• Go back to Settings and select Accounts. Add account by selecting Google.

• Once Google account has been added and setup on the phone go back to the main screen and open up playstore.

• Play Store is now displaying all paid apps in $$$ NOT in £££ and I am able to download the app successfully.