Hallo bel,
nochmal kurz zu Sóller: Solltet ihr einen Besuch des schönen Städtchens in Betracht ziehen, aber mit der historischen Eisenbahn (dem "Roten Blitz") dorthin fahren wollen - es gibt Busse, die euch ab Cala Vinas nach Palma und dort zum Busbahnhof (Estacio Intermodal) bringen, wo auch der Rote Blitz abfährt - hier Infos google maps .Busfahrt dauert allerdings. Aber Parkplatzsuche in Palma macht auch nicht wirklich Spaß. 
Ansonsten kann ich im Norden die Altstadt von Pollença und die Altstadt von Alcúdia empfehlen. Die Besuche beider Ortschaften kann man gut miteinander verbinden, da (lt. google maps) nur 12-13 km Entfernung - hier einzusehen . Pollença gefiel mir auch von der Lage her sehr gut (grün, hügelig) - Reisetipps hier
Alcúdia mit seinen dicken Stadtmauern kommt vielleicht beeindruckender über, ist aber natürlich alles Geschmackssache.
Mir haben (außerhalb der Mauern und schräg gegenüber der am Rande der Altstadt stehenden Kirche S. Jaume) die Überreste der ehemaligen Römersiedlung Pollentia sehr gut gefallen. Alles zu Sehenswürdigkeiten in Alcúdia findest du hier in den Reisetipps zur Stadt.
Es gibt natürlich noch andere schöne Städtchen auf Mallorca, z. B. Arta, welches nicht weit entfernt von Cala Ratjada im Inselinneren liegt ( klick hier) und ebenfalls nicht weit entfernt vom Nationalpark Pensinsula de Llevant ( hier zu sehen ). Kannst ja mal zu Arta und zum Nationalpark hier und hier klicken . Interessant u. a. in Arta die Ausgrabungsstätte Ses Paisses . Aufgrund der Entfernung zu Cala Vinas wäre das - denke ich - auch eine Tagestour. Wobei man ja auch noch einen Abstecher nach Cala Ratjada machen könnte.
Kannst ja schon mal schauen, was euch so gefallen könnte. 
------------------------
(Edit) Ach ja, die Strände... Mir gefallen ja kleine Buchten und darum hat's mich zu Anfang der 2000er auch mehrmals nach Cala d'Or gezogen. Mir gefiel der Ortskern und zu der Zeit waren die Strände in den schönen kleinen Buchten auch noch nicht mit Liegen und Schirmen zugepflastert. Wie's sich heute speziell im Oktober darstellt, weiß ich leider nicht.
Was Märkte angeht, habe ich leider keine persönlichen Erfahrungen. Gib doch mal über google "Holidaycheck + Reisetipps + Mallorca + Markt" ein. Dort findest du dann R-Tipps zu den Märkten der verschiedenen Orte - schaust du hier