I don’t hear/see the connection myself but I agree with others that Birdie is a universal nickname that doesn’t heed to have a strong connection. I do agree with PP that Bertie is the more natural nickname (along with Vee, Vy/Vie, Veri, Rita, Etta etc) for Verity.
If you want a stronger connection, you could use a bird name middle - eg Verity Lark as you said, or Starling, Robin, or Sparrow. There’s Wren or Dove but one syllable is harsh after Verity. There’s Paloma too but not sure about the flow, Verity Paloma - would depend on last name. There’s Verity Bird but that might give it a “verifiable bird” sort of meaning.
You could also use a B middle - like Verity Blythe, Verity Beatrice, Verity Blair etc. They could work well with Violet and Jane being more literary and established. I really like the name Verity btw.