Bahamut's Cave is a good place for leveling up also in the NES version, but I prefer the Forbidden Land of Eureka and the Sylx Tower. Bahamut's Cave is very far from them anyway. As for Dark Cloud, you're supposed to lose the first battle against her, so you shouldn't feel like you're underleveled if you can't beat her when you first fight her.