I think flying is the way to go. It's not too expensive and you don't waste so much time traveling. We flew in and out of Valencia last year and it was very easy and quick. (Good paella in the Valencia airport, too!)

By the way, the airport in Palma is really weird. I stood at the baggage claim area and thought I was in northern Europe. We arrived on a small Iberia flight, but it seemed like every other plane was a huge one from up north.