We should just have Lordaeron, Northrend and Ashenvale only then.
Heres what I came up with:
A fleet of troops were sailing through the icy waters of Northrend towards Lordaeron, when their ship was assaulted by Orc pillagers. The ship was destroyed, leaving only 2 surviving footmen. Now, the 2 survivors must make their way through the icy world of Northrend, the green forests of Ashenvale, and the outskirts of Lordaeron, only to help hold back the mass attack on the city of Lordaeron.