Paddles are only part of the hoard of objects made of organic materials rescued from what once was an Epipaleolithic settlement of the Ertebølle culture (c. 5400-3900 BCE): undamaged antler axes (right), wooden knife handles and the skull of a dog had also been preserved underwater at that location, with low oxygen levels, just off the coast.
A quite spectacularly preserved paddle:
Video of cleaning a piece of wood at the Moesgård Museum (no sound):
Source: Science Nordic.
Update (Nov 2012):
A new article also at Science Nordic discusses the paddles and how they have marks (three bars at the side) that are similar in concept but different in the detail of the execution. The shape of the paddles is also different.
My intuition wanted to see in this the execution by people connected by culture and maybe even direct family relationship but separated in time. Although not too much, maybe just one century... Just speculating a bit - other interpretations are perfectly possible, of course.