this starter kit?
Not a bad choice, but you'll probably want more LEDs and possibly some more varied resistors, depending on what you're planning to try doing with it. Unless you start harvesting parts out of old/broken electronics, you're quickly going to find yourself limited by the parts you have, and wanting more.
Personally, I started with an ARDX kit, [Sparkfun's equivalent being the Sparkfun Inventor's Kit, though it can be had a little cheaper elsewhere], which held me over for a month or so before I started tearing apart old printers and whatnot.
You've also got the option of skipping buying a kit and ordering a bunch of miscellaneous parts from somewhere like Mouser or Digikey, though that's a more intimidating process, it'll end up saving you some money in exchange for time spent figuring out what to get.
Just noticed that you're in Norway, I'm guessing you've found a supplier on your side of the ocean, otherwise, you're going to be paying dearly for shipping.
Also, having missed the original question, it's probably best to start with an Uno, unless you know you're going to need the extra power offered by the Mega. At that point, you could also look into other boards like the Leaflabs Maple, or other boards that offer an arduino/processing like programming environment for an easy start.