I'd given it some more thought.
It could be done with as few as 6 ports and two ICs.
Use 2 ea 74HC4052 to select the 4 quadrature
signals. Use 4 inputs to monitor the 4 signals.
2 ports to address the 74HC4052s.
For those inputs that previously were 0's the last time,
enable their interrupts for a positive signal.
For those that were 1's the last time enable interrupt
on a negative value.
Keep a table for each encoder. Tie a scanning routine
to a time alarm to step through each enables based on the table.
If an interrupt happens, a signal has changed.
If you only need to look at one at a time, just selecting the
address with the two ports is enough.
Dwight