My take:
First, Verification and Validation are not the same. They are actually quite different, at least in my world. When someone instructs you to "verify something" or they instructs you to "validate something", referring to the exact same "something", the resulting course of action necessary to comply with such instruction can be significantly different. Further, when it's required to "verify or validate" that "thing", it's quite different from requiring to verify it; to validate it; or to verify and validate it - because "verify or validate" means you can choose either, and suffice with that only (which to me doesn't make too much sense - the person should know what exactly they require, and if they don't they should use words like "ensure")... In the regulatory field words do matter. A lot.
Second, it's critical to note what exactly we're required to verify or validate.
Is it:
"the CAPA"...?
"the CAPA activity"...?
"the CAPA effectiveness"...? (and does that relate to the non-recurrence of the NC, or to the elimination of the perceived root cause?)
"the creation/existence of documented requirements / SOP for CAPA"...?
"the device's safety and effectiveness"...? (at what point/stage?)
There is a lot to observe/clarify here.
It seems to me that the auditor mentioned above did not care too much about these issues and didn't go to the trouble of clarifying these aspects beyond any practical doubt. Therefore, it's the auditee's job to ask the auditor questions proactively, until they are certain what exactly the NC is about and what they need to do to eliminate it (and prevent recurrence, haha). I would have actually asked the auditor "If we do <X> and show you <Y>, would we be on the right path to closing this NC?"
A prime source of guidance on this issue is ISO 13485:2016 Practical Guide. Highly recommended.