In the spirit of immersion, I switched the laptop's language to Japanese, however most of the Gnome menus remained in English even after switching the System Language altogether, logging out etc. Another profile on the laptop shows the menus for Activities, etc in Japanese just fine so it wasn't a missing package. I found the following in ~/.profile, which seems a bit heavy-handed but does do the trick. For future reference:

LANG="ja_JP.UTF-8"
LANGUAGE="ja_JP.UTF-8"
LC_CTYPE="ja_JP.UTF-8"
LC_NUMERIC="ja_JP.UTF-8"
LC_TIME="ja_JP.UTF-8"
LC_COLLATE="ja_JP.UTF-8"
LC_MONETARY="ja_JP.UTF-8"
LC_MESSAGES="ja_JP.UTF-8"
LC_PAPER="ja_JP.UTF-8"
LC_NAME="ja_JP.UTF-8"
LC_ADDRESS="ja_JP.UTF-8"
LC_TELEPHONE="ja_JP.UTF-8"
LC_MEASUREMENT="ja_JP.UTF-8"
LC_IDENTIFICATION="ja_JP.UTF-8"
LC_ALL=

Note on restarting X one is asked if they want to change the names for the default folders like Documents, etc. Personally I find it makes using the CLI a pain and don't recommend it.