After defeating the Kraken, a tangible reward would be to have a special treasure chest, the Kraken Chest, float up to the surface of the water. It would then have to be retrieved and brought aboard.
As a unique design feature, the chest could be covered in tentacles, that will repeatably smack and damage any character holding it.
The reward for delivering the chest to the Gold Hoarders should be decent, perhaps 2,000 gold or more.