"Poszukujemy kelnerki" is a correct alternative. Particularly, when the context is a job interview.
Very true. Added.
Why not "Szukamy Kelnerkę."?
The verb "szukać" needs Genitive (kelnerki), although many native speakers mistakenly use Accusative, just like you did. It doesn't change the fact that it's wrong.
We're just looking for one.
I thought genitive plural for kelnerka is kelnerek
That is right, but there is just a singular "a waitress" in this sentence.