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.

You can indeed do that, and it wouldn't change the meaning at all.

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.