Oops, my mistake, I was mixing my cities up.
How it works is that there are restaurants in Konikoni City, Malie City, and Seafolk Village. You buy a meal at these restaurants, spending various amounts of money based off the restaurant. You do not battle, you just eat a meal there.
Konikoni's gives you two Heart Scales, Malie City's gives you four Heart Scales, and Seafolk's gives you one Heart Scale but is the best value.