I'm sure your Edenwood paddle will be a stunner. Tim does some marvelous carving. For decoration ideas, not sure if you've seen the additional gallery pages on my site. On
this page, I've collected images of paddles from various museums that feature some decorative work and on
this page, I've collected images of paddles found in paintings. Those might give you some creative ideas.
In my amateur research on the topic, it seems most authentic Mi'kmaq, Maliseet, Passamaquoddy, Penobscot inspired Northwoods paddles were decorated with curved motifs etched or incised directly into the blade. An indispensible book I've found is Frank G. Speck's
Double-Curve Motive in Northeastern Algonkian Art. You can download individual chapters that clearly illustrate these mesmerizing patterns. You'd need a pretty steady hand to replicate these designs with paint but I suppose it could be done. Check out this detail in this c1878 Maliseet on my to do list to recreate.
Other examples of authentic scroll patterns on paddles can be found in
Trading identities: the souvenir in Native North American art from the Northeast by Ruth B. Phillips. Wrote a post about it
here featuring a neatly carved pattern. Rick Nash of
Woodland Heirlooms made a stunning Cherry paddle with this similar design
As far as painted decorations go, it seems that paddles were painted mainly for functionality as a preservative for the wood. The entire blade or even whole paddles could be painted with oil based paints in pretty uniform colour. Check out this
90 inch Blue and Red Guide paddle, grey Penobscot and a
Robin Egg Blue northwoods style below.
Many artists seem to have featured painted stripes or chevrons on the blades but I've not come across any existing paddles in museums (other than tiny model canoe paddles) to deem it "authentic" northwoods decoration. The only two northwoods style paddles with what looks to be authentic decorative paintings are the circa 1849 Passamaquoddy documented by T Adney and part of the Peabody Essex museum collection painted in green and white...
...the other is the c1875 Maliseet or Passamaquoddy paddle in the McCord Museum with a multi coloured decoration
The National Museum of the American Indian also has this Algonkian paddle attributed to Eastern Canada
Hope that helps and let us know what design you end up with.