Gounding for EMI and signal integrity - LED Matrix multiboard design
1) Is a very high speed multiplexing of the leds in the array
  considered "high frequency" in terms of its currents so that the
  return currents choose the path of least impedance underneath the rows
  and columns?


First off the Uno can switch at roughly 30Mhz (with a function call, if you eliminate function calls it can go faster), This is approaching high frequency territory as capacitance and inductance are going to limit the rise time of the signal. It depends on how it is wired, and the better pathway back for ground you have (by minimizing inductance), the better rise times and signaling you'll get. I would expect that this setup with jumper wire would be similar to breadboard inductance's and more like 10Mhz max. Going higher than 30-50Mhz the need for transmission lines and a solid ground plane underneath (or differential signaling) becomes necessary. 

Actually looking at the 74HC595 the max speed it can support is 5Mhz, so that will be the limiter of your design, I don't think circuit parasitics will affect you.


  2) Should a ground trace per signal (in this case per row, or per
  column) be added in the connectors between matrix board and main
  board?


Probably not necessary at 5Mhz. The thing to watch for is going to be the ground return path back to the source of the 74HC595, make sure the ground is solid (less than 100mΩ) on the wiring. Make sure the shift register has a good filter cap.