What turned out to actually do it in the end, was to make an actual purchase.
In Google wallet, I had updated all my information, as well as added a new card with my new address attached to it. This in itself however didn’t seem to be enough.
Later though, I actually purchased something through Play using the new card, and after that I could access things in Play that previously could not due to regional restrictions.
There may be some form of prioritization between different cards, so it’s possible that you need to remove your pre-existing cards as well.
Michael Hoffman mentions that it may be enough to
Click to begin a download until you reach the “Accept and buy” screen
and thus there is no need to complete the purchase. Otherwise, getting a refund after the purchase could save you the money.
For those moving countries, it might be useful to check Googles acceptable Payment methods page.
I don’t know if it’s necessary, but user Ikon also adds this after adding a new card:
Went to the apps settings and wiped Play’s data. Rebooted phone, accepted terms again for Play and now I can install
I called Google Play support and they sent me these instructions:
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
2) Delete all of your payment methods from Google Wallet, and only add
a card to one with a billing address located inside your desired
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.
Following these instructions allowed me to install apps limited to my new country without making a purchase.
The settings you have to change are at wallet.google.com. Sign in with your account, go to Settings, and change “Home address” to your new address. You might also have to change your phone number, and your default “Billing and delivery address” in the second tab.
Note that this will not let you buy contents from a country you don’t live in, since you need a credit card and an IP from that country.