We go MTB’ing every year in Mallorca. Can thoroughly recommend it.
We bought this guide http://www.rockandride-mallorca.com/mtb-guide-fuhrer-rutas-tour/
You don’t need to buy a trail map (unless you want to) if you use the guide as the instructions are excellent. We actually bought it twice as some new rides were added this year!
The riding in Mallorca is definitely challenging, beautiful and fun. I found it knackering but it depends on your fitness I guess! Not much flat. Lots of rocks, switchbacks, forests, stunning scenery, secret beaches, remote villages.
The guide I linked to has one Palma ride, which I haven’t done. The rides in the north (starting from Soller, Esporles, or Lluc) are tremendous so I would say definitely worth hiring a car for.
Hope you have a lovely time!