few places I can recommend having been over last week with the kids ;
Can Juame, Cala Vadella, great paella, lovely spot right on the beach, can see why it's got such a good reputation, cheers Stivi.
Yemanja, Cala Jondal, Sunday lunch, dropped in on the off chance and although it was fully booked, they found us a table, not cheap but top quality food and location.
Can Pa, Cala Vadella again, great tapas, place was buzzing with locals early evening, prob my fav meal of the week.
Can Vincent, Cala Carbo, nice spot for a decent lunch if you're spending the day on the beach.