Indeed, if the only thing your MCU is doing is decoding this, then polling is the way to go. Interrupts only make sense if your MCU has to also do something else.
Any MCU should be able to decode these at thousands of RPMs, unless your routine is complex. I have a routine that has 3 lines of logic code (and immune to switch bounce). Thats a pretty tight loop.