I see no realistic way to defeat them.
Throw rocks. I don't remember exactly how big my 2 L2 bosses at level 1 'Master Hero' were, but that worked ok, with some fireball/ice cross for knockback.
Q: What do the *s on the overworld map mean?
Q: Is it normal for a cave entrance to be under water? (Fortunately the next cave was _not_ entirely flooded, but it did make it hard to find). For that matter, you can come out into water, or in midair and fall into water. all normal?
Q: can you rescue people that you find in the caves, or do you have to go home and send somebody else?