One of the benefits (I think) of having a 100 pin package is that you don't need to multiplex your IO. On the 328, every pin had multiple functions. If you examine the 2560 you'll note several pins have only one function. This is primarily due to the fact that the underlying AVR architecture is essentially the same. Larger memory and a few extra peripherals, but that's it. Back to your issue, there are 32 pins available on the 2560 for interrupt processing, so if you're unlucky you pick the wrong pins (as you did).
PC0 - PC7, which correspond to pins 37 - 30, are connected to the ADC and by virtue of the larger pin count don't have to share. To further confound you, pins 16 and 17 do not interrupts either.
Your encoder really does need to be serviced by interrupts, buttons are not that big of an issue. You will however, need to bridge your connections from pins 31 and 32. You can place those pins in a high Z state with your code and attach your interrupts to the bridged connections. If you're using the chip, pins 31 and 32 (Arduino) are pins 59 and 58 on the 2560. Your nearest interruptible neighbours are at pins 63 and 64 (2560) corresponding to pins 15 and 14 on the Arduino (which also happen to be Rx/Tx for serial3).
If you're using the chip you may opt to use pins 66 an 67 (PJ3/PCINT12, PJ4/PCINT13) which do not share with anybody and are not terminated on the Arduino. Not sure but you may also need to do your own port mapping on the last two as the Arduino board package may not include them as they're not terminated.