Sitting even further north than Denmark, the OP did say that their melons are imported. Although it's possible to grow them in Denmark (especially in a greenhouse) perhaps it's not commercially viable.

Regardless, I guess the OP just needs to find a better grocer, local "fruit mongers" up here in frigid Sweden certainly routinely handle watermelons that are way bigger than 3 kg. :)