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.