Hi Bryan, lots of people use Sitka Spruce for the shaft. It's very straight; commonly used as (sailing) spars for that reason. It's also expensive/not easy to get. I happen to like the look of Spruce combined with WR Cedar.

I used plans from Mac McCarthy's Featherweight Boatbuilding book for this Euro paddle. Nick Schade's Book has similar plans. The plans (as I recall) will give you 'offsets' for each inch of the paddle blade and some good ideas for shaft construction. I've also seen lots of good ideas on this BBS which you may be able to find in the archive.

Also, consider a Greenland Style; that design looks a little odd to me but otherwise has a lot going for it.