500 calories a day is a decent deficit. If you drop too much, you're going to compromise lean muscle mass. The slower your deficit, the more fat vs muscle you'll lose. Do you lift weights? Do you have heavy exercise days? If you do, I recommend cycling your calories - eating maintenance on days you lift or exercise heavy and cutting harder on days you don't. If you work out 3 days a week, cut cals by around 850 on days you rest and eat maintenance the days you don't. That'll help ensure you retain or even build muscle while losing fat, and it'll put you at the same deficit.
Responding to Neckhammer's post, don't let him mislead you. There is no metabolic advantage to a ketogenic diet. It all comes down to the calorie deficit, and if you keep your protein level equivalent, it's not really going to matter what your fat/carbs breakdown comes from as long as you pick whole food sources that keep you full (don't go comparing steak and eggs to flour and sugar). Do not underestimate how stressful on your body a prolonged diet of meat and vegetables can be. Danny Roddy covers a lot of this in his "Your Gut From Hell" series.
Your Gut From Hell, Or: Why The Evolutionary Model of Intestinal Health Is Goofy — The Danny Roddy Weblog
Your Gut From Hell Part II: A Ray Peat Inspired Digestive Primer — The Danny Roddy Weblog
If you're really brave, look at his "Becoming Stress Proof" series.
The orthodox paleo view is ridiculous as it's a completely assumed diet, and it treats carbohydrate as optional and meat and vegetables as king. While it's true your body doesn't need to directly consume carbohydrate to survive, what's essential and what's optimal are two entirely different things. It doesn't address the major issue of excess cortisol and the insanely imbalanced ratio of calcium to phosphate in the Whole 30-style diet. Look around this forum for threads about hair loss and body chills. It's real.
We may not know what the ideal diet is, but we do know that life generally evolved around the Equator where leaner game meats and fruits/tubers reigned. We also know that the majority of traditional civilizations still in existence today consume more carbohydrate than fat. There are very few low carbohydrate societies in comparison, and you probably didn't descend from those societies since the people didn't emigrate to cold climates where fatty game was common until very recently (comparatively).
Just some food for thought. Ultimately, no one can tell you what to eat. You need to find out what you feel best on. But it's a reality that you may feel best eating more carbohydrate than you think. Just choose quality sources of starch and seasonal fruits.