Hi - it can be as cheap or expensive as you make it! We too struggled to get decent prices on self catering, but managed it. Where are you staying? then i can work out where is local to you. There is your usual KFC, Burger King if you want that, chinese buffets for all u eat for 12 euros, places that do 3 course for 13 euros, however you do only get what you pair for, our favs are El Toro, which is a little more expensive, but the food is amazing, so maybe eat there a couple of nights, also we like spanish rest, on the corner of the main road towards beach, again they do set meals, but there tapas are good priced, and the paella is lovely. they locals all eat there, which is a good sign i always think. You can eat reasonably in most places, i find it is the wine etc that bumps it up. You can always go to the port, there is nice places there, the mexican is lovely, but it is more expensive down there. dont bother desert when you eat, take a walk up to the bridge for the crepe man, he is famous for it, they nutella and cream crepe is to die for!!! if i can help more, let me know, we are out in Alcudia quite a lot as my brother works over there in the summer.