"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.
How to say this for kelner? I tried "kel
"Szukam kelnera", but we don't accept the masculine version in this excercise.