"I paid two thousand yen at the restaurant."
Yes, を is grammatically correct, but usually omitted. When speaking, を is very commonly omitted from almost everything. The only verb that I can think of that grammatically shouldn't use を is かかる, as in 時間/円 かかる。
My guess is probably not, but because I learned my Japanese conversationally, I'm curious whether this is just commonly omitted and in fact grammatically required, it's grammatically incorrect to have a particle, or it doesn't matter either way.
The root verb "to pay" is 払う (はらう). The form we have in this exercise is the polite past tense, and 払って is the て-form of the same verb.