Background
I have a player who has a level 8 Half Orc Paladin (STR 16, CON 18, CHA 14, Vengeance oath, Sentinel and Orcish Fury feats, no magic items) whose backstory involves running away from his home town when he was young (12 or so?) when his orcish father turned up with a horde of orcs looking for him. He hasn't seen them since and he's now in his 30s or so.
I was going to have his "father" turn up with a horde of orcs (15 or so) and demand his "son" back, mirroring his backstory. I was planning on guiding the narrative to the paladin PC having an honour duel with the Orc War Chief (MM, pg 246). I have a player and group who are into narrative over gaining XP (in fact we're using milestone XP) so I think this will go down well (though if they just decide to fling fireballs at the orcs, then that's what happens; I'm not going to railroad this too hard).
Given that this will be a BIG backstory moment for the player, I want to make sure this duel is suitably epic. I want it to be winnable, but also deadly. It should be a skin-of-his-teeth victory. I imagine (since Chaotic Evil orcs don't have honour) that when the War Chief starts to lose, the other orcs might join in, or if the War Chief ends up on < 10HP, he might even try to run away, but we'll see how that goes. I imagine the rest of the party will join in if this ends up happening, but until then, I imagine the duel will be a one-on-one fight between the paladin and the War Chief.
Problem
Anyway, if I want this fight to be deadly, a CR 4 monster probably isn't going to cut it compared to a level 8 paladin (this is based on the encounter design table in the DMG, pg. 82). But at the same time, I like the War Chief's abilities and flavour and such, so I'd rather not pick a different creature.
Ideally, this monster should be about CR 6, but I wonder if just bumping up his health, AC and attack bonus will be enough, or whether this wouldn't really make him that much more threatening over the course of the duel (this is me trying to follow the table in the DMG, pg. 274). Even though this PC has none, magic items exist in my world so the War Chief could have one of those, but would a +1 weapon or whatever really change things that much?
Question
How can I change the stats of the Orc War Chief to increase the CR from 4 to 6, without changing it drastically like adding spellcasting or lair actions or otherwise messing with the monster's flavour?