The region locking is even more aggravating if you use a console since it has to match the region of your PSN account or things start getting complicated. I use a Japanese PSN account on a Japanese PS4 and had to make a separate UK account to be able to buy the game here. I know this is exacerbated by Sony's restrictions but it makes me a little anxious as a former PS2 FFXI player (IIRC only Japan got the full set of expansions on PS2 for that game).

I believe that S-E Europe and S-E USA are effectively separate companies so they'll probably have to refund you for the original purchase and then you can buy it again from the EU store. I cannot imagine a situation where they would refuse to do this since it's entirely their own fault that their company is so confusing. I'm sure you've worked this out by now but just in case (or for the benefit of other readers in the same position) I can confirm that their customer services team is usually pretty helpful.