https://wiki.project1999.com/Shaman_Epic_Quest has everything you need to know about the epic. But to answer your question, you might want to wait just a few levels more, as Capt Surestout is level 20. Also the next step (Test of Patience) potentially exposes you to level 40+ sharks.