In terms of levelling Valbar need to get to level 10 to become a Baron. However, since he gets the last 3 for free, he only Neede to reach level 7, or rather, he needs to level up 6 times.
The first map Valbar takes part in is the Cantor boat map. Valbar is able to tank Revenants for days, so as long as you arent trying to LTC, he will be able to get an easy level off of the revenants, Maybe even two levels if spawns are consistently large, an optional 2nd (or 3rd) level can be gleamed if Valbar kills the boss, but he is not the best choice for this, as Celica may still need Seraphim. Due to the many kills he gets Valbar should obtain 40-50 bexp. So we will assume he is at level 2 with 90 exp.
There are now 2 options for which map to take, however it is recommended to battle the pirates, first, as this will make it easier to promote Valbar. Valbar easily beats this whole map, meaning he will be able to level up again and should be given the bosskill unless Celica has not learned Seraphim (in which case, what are you even doing) for a 2nd level this map. He should gain 20-30 bexp. We will assume that Valbar is now at level 4 with 20 exp (blaze it Valbar) He needs to level up 3 more times to promote.
You could go onto that Arcanist boat next but 1. Valbykins doesn't eat mages and 2. You don't need to. Onward to the Seabound shrine. Valbar will gain like 6 exp total from the necrodragons, unless he kills one in which case he gets 30 ish exp for the small one and 50 for the boss, don't bother with that however as it requires some specific damage outputs from your mages to set one of them up. Valbar is now at level 4 with 26 exp (bye bye funny number).
You will find 2 bonewalker encounters and 1 revenant in the first room and 1 revenant, 1 bonewalker and 2 gargoyle encounters in the second (disregarding rare spawns). Valbar will be able to get 1 level in 2 (individual) bonewalker encounters from kills and bexp, easily enough and shouldnt have any trouble getting some good exp from the rev, at this point he will be around level 5 and 60, he wont level off the revenant in the next room, but if fed the full encounterhe should come out at level 5 and 90 give or take a few points, he will come out at either 6 and 10 or 6 and 40 depending on whether you fought them one or two encounters at a time. The gargoyle encounters will most likely be faced at the same time, so just send Valbar straight in to get that epic victory royale, but you gotta be quick kid, and move all of Celica's crewmates away so as not to divert attention from Valbo. He hits level seven, eats an apple and drinks some water and bippidy, bobbidy baron, there you go.
Now as for Valbar over Palla, it comes down to Palla not really needing her promotion at that point (the only thing that Falcoknight significantly contributes to in act 3 is 1 rounding summoned gargoyles, but expel does that anyway) she doesnt gain any attack, only gains 2 spd (for a whopping 12 speed unarmed about as fast as an unarmed mercenary) and she has enough base HP and a 50% growth that she only gets on average of 4 hit points on promo. She gets 4 def and and 7 res, the latter of which sounds impressive but this is SoV where magic enemies are either too weak or too strong for 7 extra res to matter. The extra point of move doesnt even help get Palla anywhere she needs to go any faster.
Baron Valbar however with his chunky 18 defense takes a single point of damage from every Melee attack thats' not from Deen or Blake throughout the entirety of act 3 without having a Shield equipped. This allows Valbar to absolutely demolish the Archer fort, the Deen map (leather shield Valbar takes 1 damage from Deen at base) and as long as you take care of the witches and arcanists, the Grieth map as well, all of which FalcoPalla struggles to survive in. Sadly, the Mila temple is a bit to mage powered for Valbar, and act 4 is just not friendly to armor knights, the exp shrine in the tempel basement will allow you to get a falcoknight for act 4 where they are actually good. Also give Valbar the Dracoshield for Duma Tower Funnies
Thus, Valbar is a better user of the Seabound exp fountains and apple, than Palla.
tldr Armor >>>>>> Flier