This looks really great RedDragonJr. It's a nice-looking map that would be very easy to understand in a game, and help all players visualise the encounter. It does exactly what it should do.

...am fully aware that rocks look bad...
Your rocks look great! I notice you have a light dropshadow - why don't you double it up if you want the rocks to pop out a bit more. If you instead want the colour of the rocks to be more yellowy-orange like the desert, you can easily do this: 1) duplicate the rock layer & place above; press the button that freezes pixels; choose sandy colour and drag it into the layer so rocks have 1 block colour; change layer to overlay or grain merge and alter opacity to give sandy vibe to rocks.

...cart marks don't even look like cart marks...
True! But cart-marks are really hard. I'd probably use a gravel texture, and with a layer mask make two sinuous lines of gravels.

...and the palm tree looks too out of place...
Have you though about making it four-times bigger? It's not like anyone was going to do much in that corner of the map anyway. I think the reason it looks a little out of place to you is the scale between the sand-dunes, tree and rock. Making the tree bigger and perhaps selecting a sand-texture without sand-dunes might sort this out.