No, that's the proper amount of damage that your characters should be doing.

However, if you feel uncomfortable with this, then go ahead and level up (whouldn't be that hard considering the area, EXP gain/statistics). As most people who play the game, apparently having Holy as an attack option by this point in the game is available to them. Don't go that far.

As far as Ultimate Weapons are concerned, you should have already gotten Tidus' (if you want the ABSOLUTE EARLIEST POSSIBLE), which is almost completely obtainable in the Calm Lands (you should have already gotten the Sun Crest, otherwise, you need the Airship). Auron's cannot be obtained without the Airship, along with Lulu's, Yuna's, Wakka's, Kimahri's, and Rikku's.

However, to attain Tidus', you aren't that good enough at playing video games to get it at earliest possible. This is fact, unless you have already beaten the Chocobo Trainer and gotten a time of 0:00:00, and gotten the Sun Crest, and went back to Macalania to power up the weapon.