For what little it's worth as evidence, the paddles (of Maliseet and Micmac manufacture) I've seen in museums have been hard maple, almost certainly sugar maple.  I found (and traced) one Micmac type in a New Brunswick museum made of an attractive birdseye hard-maple.  I own a paddle made for my great-grandfather by a guide and canoe-builder in Presque Isle, Maine, about a century ago.  This paddle is also of hard maple.  (The guide's name, by the way, was Curidineus Hoare, according to my Uncle Howard when he gave me the paddle.  I was skeptical of the story but, sure enough, the census of 1900 lists one Curidineus Hoare, guide, living on State Street in Presque Isle.)  I've made a couple of replicas of this paddle and use them frequently.
I've made paddles of white ash, sugar maple, red or white spruce, and cherry.  I think maple is the toughest wood.  My favorite paddle is of cherry, patterned from a tracing of the above-mentioned birdseye Micmac type.  To me, the cherry feels lighter and more pliant.