If you get the running popup, but afterwards don't see the Running option in the menu, you have to close the app manually. By pressing the home button twice and then swiping Spotify up and out of the screen. Afterwards, running is active in the menu. At least, that's what worked for me.
I'm in America and I was having the same problem as you. I couldn't find Running in the side window. I came across a response saying that Running is still available, you find it under Browse now. Scroll down through the Moods and Genres and you'll find Running. Hope that helps 🙂 This solution is credited to patrozoo.