--- Quote Start ---
In order to constrain I/O timing I need the setup and hold times of the device I am interfacing with.
Usually that can be found in the data sheet of that chip.
But what if I am interfacing with another FGPA? Assuming that I design both FPGAs, so I have the design and synthesis of both sides.
How do I determine the setup / hold times?
--- Quote End ---
As you realised FPGA is configurable with respect to setup/hold.
For two fpgas you can set input delay of destination device to some arbitrary values and see report for achieved tSU/tH (datasheet)