In my opinion, both diets are healthy if a person carefully studies the positive (and negative) facets of each. Each can promote weight loss.
You could spend the next ten years of your life researching not only the pros and cons of those two diets, but of several others, too. The bottom line is that health experts for years have been doing research, offering suggestions, and engaging in arguments about what is a healthy diet and what is the healthiest way to lose weight eating or not eating certain foods.
I have spent many hours the last three years, intermittently, reading books and researching on the Net for what constitutes healthy eating and healthy weight loss.
My conclusion: to lose weight we need (1) to exercise intelligently and (2) to burn more calories than we consume, but to do so in a way that does not make for unhealthy side-effects.
I have researched this topic for quite some time now because I have also debated going vegan. In my studies I have found that quite often vegans begin to notice their health declining over time and eventually switch to a more paleo-type diet (or begin incorporating animal foods) and their health improves dramatically-- even if it's just a couple eggs or seafood a few times a week!
Here's a few of my favorite sites if you're interested:
http://rawfoodsos.com/ (Denise Minger's blog-- she's famous for debunking the China Study and other pro-vegan studies-- very detailed and lengthy discussion of why these studies are biased/wrong-- she is VERY THOROUGH!)
http://letthemeatmeat.com/ (Interviews with EX-vegans, really interesting)
http://30bananasadaysucks.com/ (Recent site ran by an ex-vegan whose health and physique has improved dramatically since switching to a paleo-approach. The site focuses mostly on the 80-10-10 diet, and has lots of stories and videos from people who's health improves after they ditch all the nonsense that they've been given and start focusing on what THEIR body needs)
http://www.my-healthy-eating-secrets.com/pale o-diet.html (Heather's experience-- she was vegan/vegetarian for over 14 years. Her story is what caused me to begin questioning the vegan diet)
Basically the point of all these sites is to help separate fact from fiction in the vegan community. The vegan diet promises EVERYTHING-- health, happiness, world peace, happy animals, sustainability, natural hygiene, energy, weight loss, better hair, better skin, better nails, no body odor, youthful appearance... etc. You rarely ever hear anything bad about a vegan diet... that is until you dig a little deeper (and yes, weight gain DOES happen on a vegan diet)
I personally follow a paleo-style diet-- but I do incorporate a lot of vegetarian items such as tempeh, sprouts, and rice protein. I also try to keep my diet as high in vegetables and anti-inflammatory fats as I can. I don't like to promote one diet over the other, but paleo is very versatile, nutritious, and very easy to lose fat on (it also does not have to be "low carb")
However if you do decide to go vegan than you really need to do your homework. It's hard to thrive on the diet without being very aware of what you need, and making sure you supplement in the nutrients that you lack (namely B12 which can only be obtained from animal sources). Personally I believe any diet that absolutely requires supplements in order to work is a big RED FLAG. I don't believe a vegan diet is healthier (let alone natural) for humans; but if your morals stand in the way it is possible to do as long as you research and plan.
I am currently reading "Drop Dead Healthy" - it is about a man's journey through diets, exercise plans and such to be "the healthiest man on earth". In his book he talks to developers of a lot of different "diets" He does the very low calorie diet he does the paleo, vegan, raw, Zone, Adkins and everything else. I am only about a 1/3 of the way through, but I heard him on the radio talking about his book and he said from his experiment and how he felt he basically uses a small plate, eats with a shrimp fork, chews his food 30 times, and incorporates a lot of the paleo, vegan and raw into his food choices.
He says in the book that he thinks the biggest contributor to his weight loss was just using small plates. He said our plates have grown 2-3" in diameter over the years and just using smaller plates makes you use smaller servings.
I found for me the weight loss came fastest when I stopped eating processed foods, ate enough protein to fuel the muscles for weight lifting workouts. Enough good carbs to fuel the workouts. I don't eat whole wheat bread cause its full of additives, but I do eat Ezekiel bread. I use sweet potatoes now and steel cut oats. Lots of fresh fruit and veggies.
I also don't do sugar. I only get sugar from the fruit I eat.
Paleo would be healthier if you compare it to a vegan diet that includes processed foods, sugar, and an overabundance of grains.
If you compare paleo to a healthy vegan diet of unprocessed foods and with controlled carbohydrates, either one can be a good choice. However, as carmenxox said, there are some potential problems with veganism. I suggest that the only good reason to follow a vegan diet is if you do so for ethical reasons. It is not the best diet for overall health (all health considerations, not just weight loss).
Either a paleo or vegan diet could promote weight gain if you eat too much.
And if you do go vegan, ensure that you are supplementing with a B-vitamin complex, especially B-12 because that only comes from animal sources and will cause you to become anemic. Otherwise, if you do a whole-foods, low-no sugar, no processed crap vegan diet it can be very healthy.
What both have in common is the removal of processed foods, white flour, refined starches, sugar, soda, alcohol, cigarettes, and other junk.
This step alone will pretty much guarentee results on ANY diet that you choose to follow.
>>aka: EAT REAL FOOD
This, this, a thousand times this.
As long as they're balanced, you can be healthy on both. I'm not a vegan, but I'm sure their health declines only because they rely too much on processed junk.
I think they can BOTH be healthy, but I like to think of it this way: humans didn't exactly evolve to only eat rice milk, tofu and lentils! So while I enjoy such foods, I also eat lots of eggs and fish and dairy (some, it doesn't always agree with my tummy!!), and am also starting to introduce meat.
I have been a vegetarian, and I feel MUCH better now I eat a more balanced diet. I would take research, and what others say, with a pinch of salt - we're all different, and do better on different amounts and types of food!
There are positives and negatives to both diets but personally I believe Paleo to be healthier of the two. Vegans sometimes don't get enough protein, which is essential in the body, because they're unaware of where complete protein sources come from. (Quinoa, Hemp... Rice and Beans are all complete proteins - the latter when paired together). The paleo diet on the other hand focuses primarily on protein (as well as lots of healthy fat) so people who eat this way get the nutrients they need.
That being said, each to their own. For me, the paleo diet is the way to go.