Hi.
The language error is weird, because in both the languages I have installed (en and pt), I have that string in the language files, so that should have worked. Anyway, doing an override fixed the issue (although it was suposed to be working unless I'm missing something).
Now about the error itself, I figured it out. I made a "Account Management" VirtueMart menu link named "Register" with a Guest permission (only to people that were not registered, but hidden from people that were already logged in) so people could fill in the adress details on register. The problem was that setting shipping adress details would redirect to that menu link (probably for SEO reasons) and that was not allowed.
TL;DR: Changing the permissions of the "Account Management" menu link to public, or unpublishing it resolves the issue.