[Stratos]

Tomi is near the exit of the temple in the Core District. A short fellow with a knife.

You can buy or find scrolls of Knock, but since you're a Paladin, you can't use them. Your best bet is to either use Tomi, or simply bash the chests. Bashing will be much easier once you get your hands on a weapon that does some form of elemental damage. Talk to the smith Marrok under the Knight's Arms, he can make some for you.