After you put in the correct password in the Sunken Ship, you have to battle your way past King Calamari.
Defeat the Tentacles
The battle starts against three tentacles. If a tentacle lifts up off of the floor, you can push the button to try to block the attack. The tentacles can also grab a character and take them out of the battle for one or two turns. They will have the "scared" status upon their return.
After you defeat the first set of tentacles, you move forward and battle a second set. It's just like the first set.
After that, you battle King Calamari itself, along with two more tentacles. King Calamari is weak to Mario's Super Flame, so use that if you have it. Geno Beam works well, too.
King Calamari has a regular attack that you can block. It can also attack with Venom Drool, which inflicts poison. It also has a Drain Beam attack, which does low damage to all three characters. Ink Blast does a lot of damage to a character. Sandstorm does a small amount of damage and inflicts "scared" on everyone it hits.
After Calamari
After you defeat King Calamari, you can explore the second part of the sunken ship.