I'm terrible with languages... it will probably take 5 years to reach 'conversational' levels.
My company is extremely international, and all business is done in english, so there is no problem. Other companies I interviewed with did bring it up as a problem. Startups seem to care very little, major corporations care a lot.
I would think that since you are living in the country if you take a night course (or something equivalent) you could probably learn a lot quicker than someone living outside the country.
Immersion helps, but it's pretty easy not to become immersed in Scandinavia, because everyone both speaks good English, and switches to it quite quickly when they realize you're a foreigner. It's possible to ask them to please speak Danish/Swedish/Norwegian because you're learning, and many people will then switch back, but the immediate switch to English is basically default (especially in Denmark).
I've lived in Denmark for 2 1/2 years and probably have had less real need to speak Danish here than in the 3 weeks I spent in Spain! More Spaniards are either unable or unwilling to speak English, so that trip was much more immersive language-wise, in that I actually had to interact in Spanish.
Don't be to hard on the Spanish. I lived there for some time and can attest to that most Spaniards really would like to improve their English but find it incredibly difficult to do so. This is especially true for the spoken language.
My personal theory is that Spanish Spanish (i.e., from Spain) has a range of spoken sounds that is to a large part complimentary to that of English, thus making the transition between these two languages particularly difficult. (Note that there is significantly less of a difference between the sounds of American Spanish and English).
My company is extremely international, and all business is done in english, so there is no problem. Other companies I interviewed with did bring it up as a problem. Startups seem to care very little, major corporations care a lot.