Paladins don't run around with a giant P on their spandex suits. They aren't going to know whether its a paladin, eldritch knight, cleric, wizard with armor proficiency or other combatants. They might figure it out eventually, but it's not going to be automatic or even necessarily in the first few rounds of combat.
I know you're juggling a lot of responses here, so I'll describe the scenario again. (Also, paladins usually
do have a giant 'P' on their outfits, in the form of a holy symbol or other identifying religious markings. Maybe a cleric, maybe a paladin, but it certainly narrows the options down. )
BBEG with
counterspell sees a warrior (again, likely marked as a religious class of some type) make a melee attack and
immediately start to cast a spell. A high INT BBEG knows there are very few, if any, spells that can be cast this way, so it's a safe bet on their part that the warrior-type is casting a
divine smite spell. In the grand scheme of things, that's not going to be a priority to use
counterspell on, especially if the enemy party has at least one (possibly more) spellcasters who could cast something targeting the BBEG at range, and/or the BBEG's party with an area effect. That 1st level
divine smite spell simply won't be worth the effort, most of the time, especially if the BBEG isn't the immediate target.
Remember, counterspell is a limited resource in terms of spell slots and actions within a round. So, the BBEG can only counter one spell each round, and only a few times during the entire battle (especially if he wants to use any of his other spells). They have to choose strategically between all the spellcasters in the enemy party, which again, is going to put the spell-casting warrior lower on the list.