In a society built around privacy of thought, easy and consequence-free mind reading is too powerful. We need to make it either harder or have consequences, either by changing how mind reading works or how society does. Some ways of doing that:
Mind Reading is Hard
There's many ways to do this. Maybe it's hard to drill past the irrelevant surface thoughts, maybe mind reading is tiring, maybe it's hard to focus on one person and turning on the power means getting everyone's thoughts at once. I think one of the most interesting ways to make it harder is to just take into account how diverse minds are. In humans alone you have all sorts of mental and psychological disorders that affect how you think, let alone different cultures and languages. What happens if you mind read someone who thinks in a different language? Maybe you could see images, but it'd be damn hard to understand what's going on. Now add in the fact that you mind not even be mind reading someone of the same species. Need to pull information from that half-demon orc shaman? Good luck!
These things don't make mind reading impossible or useless, they just bring it more in line with other interrogation and investigation techniques.
Mind Reading is Stigmatized
"This guy knows where the dread necromancer is hiding, but he won't tell us a thing!"
"Stand back, I'm going to read his mind."
"...Out. Get out of our village. Right now."
This works best if you can't hide mind reading, like everybody you're scanning can tell or your eyes glow freaky colors or the like.
Muz pointed out that it'd be harder to find a society where this isn't the case. Imagine how you'd feel if somebody stole your diary and set up a bunch of webcams in your bathroom. Mind reading is worse.
Mind Reading is Loud
(from Keshlam) Reading a mind isn't like reading a book. It's more like forcing a person to broadcast their thoughts and tuning in. This means it's very, very hard to keep a reading secret: sensitive people nearby will be able to tell that it's happening, good readers will be able to eavesdrop on the reading, and the great ones will be able to spy on you, too. Enemy psions and psychic predators can hone in on the signal. Good luck hiding.
Mind Reading is Wrong
Maybe when somebody reads your mind you can feel them almost rip out your thoughts, leaving holes in your memory where you know something was important but now it's gone. Maybe when somebody reads your mind you feel exposed and vulnerable and terrified. Maybe when someone reads your mind you are forced to relive vast swaths of your life, leaving you perpetually unsure of whether you're back in the real world or just trapped in a memory. Whatever it is, getting read hurts and is wrong.
Mind reading is like any other temptation. It makes solving problems a lot easier, but you better think long and hard about whether it's worth the price.
Mind Reading is Dangerous
Instead of / in addition to mind reading being bad for your target, it's bad for you. Scanned memories become your own memories and if you're not careful you can lose your sense of self or think you're somebody else entirely. Your target can fight you off an leave you mentally scarred if they win. There's rumors that some criminal organizations have been training 'mindbombs', people who undergo unimaginable pain and lock up the memories. Peer into the wrong mind and you'll lose your own.
Short answer: You do not.
You say that he does not fit in with your plans as a DM. But the thing about being a DM is NOT that you tell a rigid story that your players walk through: instead you put them in a series of situations, see how they react and frantically try to fit your story to it. I understand that your story is your baby and the PCs all try to spike it to the floor like a bunch of murder-hobos would do with an orc baby, but that's how it goes.* One of the most difficult things as a DM is to let go of what you want to do and instead act on what the players do.
Not to say that there are no alternatives to your problem.
Talk to the player. Murdering a PC just because they "do not work with your overarching plans" is a downhill highway to getting a pissed off player. Instead, talk to them. Discuss this problem with them (though please LEAVE OUT THE MURDER PART) and see if you could reach some kind of compromise. What is this reason this Warlord is a 40 year vet and still only level 1? What is his actual story? Again, do not bring up killing them: the character is as much the player's baby as the story is yours.
Roll with it. One of the most interesting things as a DM is dealing with the bizarre stuff your players come up with. See what they want to achieve (especially the player in question), and try to match your story with this.
Talk to the players. The most difficult one. For the players, roleplaying is about experiencing a story, not being told one. They want to take part of it instead of being along for the ride like a rollercoaster. Ask them what kind of direction you want to take the game in, see how this matches your kind of story, and try to match it. If it works, great! If not, I'm afraid you'll have to compromise.
(* This is not to condone the murder of babies of any kind. Killing babies is a Bad Thing.)
Best Answer
Let it Go
So, you feel your characters should behave a certain way, but everyone's having fun. I'd say let it be. Collecting trophies off victims is not out of character for a Barbarian. It doesn't seem as though the player is suffering from "My Guy Syndrome" (acting in a disruptive way and justifying it by saying "that's what my guy would do"). By the way, collecting body parts is so common a way to say "my dude's a badass" that it's a trope. It would be psychopathic to do in real life, but when a player says they want to do it in a game, I yawn a little bit.
Let the Fiction Determine NPC Reactions
But you are correct about one thing: NPCs should respond to your Barbarian's penchant for body part collection as that NPC would. That means a merchant in a civilized settlement may respond with disgust, while a bandit may be terrified by the Barbarian's prowess (probably the effect your Barbarian player is hoping for). The Barbarian may well be barred from certain settlements or even jailed. Conversely, another Barbarian, with their own body part collection, may well be impressed by your Barbarian's trophies, and may want to compare trophies.
The important thing is that you respond to the Barbarian's choices based on the story, and not in a punitive manner, e.g. "Because you are doing something I think you shouldn't do, bad stuff will happen to your character". NPCs should act based on their personalities and a common sense interpretation of the fiction.
When the Fun Stops
Now, all of this changes the moment one of your other players (or you, for that matter, you're a player too) stops having fun. Is this behavior making it difficult for players to enjoy the game? Is it making a player have an honest-to-goodness reaction that is causing them emotional distress? If so, it's time to talk about the behavior out of character, player to player, human to human.
My answer is predicated off my interpretation of your question, which is that: it's going ok, but it just seems like something I shouldn't allow, because DnD, and alignments and all that. I just don't think you should let preconceived notions of how the game is supposed to be interrupt you actual enjoyment of the game.