Samsung Pay requires a SIM card to work, and it requires it on the first boot.
My solution was to put the SIM card in and then reset* the phone.
When it started with a SIM card in it, I saw "Samsung pay Sweden" pinned to the home screen (Swedish SIM card). It then worked flawlessly.
Why isn't this bug fixed yet one could ask, but there you have it.