Incremental encoder - polling or interrupts?
Now that being said, my question is as follows: which option should I chose?

Poll at &quot;high&quot; speeds where the poll has a likely chance of catching an event rather than being wasted, and interrupt at low speed. Both methods suck equally though.

A third option could be to initialize a timer interrupt, and in that interrupt routine, I could check for the pin states. This interrupt could occure twice as fast as a state change would occur at the highest speed, so I guess I would not miss any changes with this method as well.

No! No! Timer interrupt is pointless. You might as well just poll and not have the overhead of the interrupt context switch. You would just have to make your main loop tight, or insert multiple polling points in your main loop. If you are going to the trouble of interrupting, just interrupt off the directly GPIO.

If I were to develop the whole thing from scratch, I probably would hang one channel of the encoder to an interrupt pin on let's say port B, and in the ISR I would check for the state of the other pin. To me, this seems to be the cleanest solution, this method probably catches all position changes, correct me if I am wrong.

No, use a different PIC with a QEI. Might not be too late to switch for a code and pin compatible PIC.
EDIT: I actually looked at your encoder datasheet. Your encoder is super low res. I'm used to encoders with thousands of pulses per revolution. For you, go direct GPIO interrupts, no question.