Neither Knight nor Thief really offer Severa anything, skill-wise. Having a good skill selection is more important than stats - pair Cordelia with someone who passes Myrmidon. Stahl is a good alternative to the standard Lon'qu x Cordelia pairing.
Vaike x Yarne gives Yarne access to Wrath and Counter doesn't it? That would work out nicely even if thief overlaps.
EDIT: Didn't see you mention that Stahl/Lon'qu are already paired. Oops. Are Gaius / Gregor available? Their stats aren't quite as good, but like Stahl and Lon'qu they allow Severa to go Myrmidon.
Yarne can learn Wrath and Counter regardless of father; Vaike can give him only Fighter and Hero (so Sol). --- "A few? What'd ya mean 'a few' ? What maybe a few to y'all was everything to those who died!" - Cait Sith