--- Quote Start ---
I've tried to set phase difference to -10.2ns. This obviously helps TimeQuest to show me, that there are no setup violations made, but if I try to upload Nios design (at least it allows to try to upload!), it says that verify has failed between some addresses... Now trying other options.
--- Quote End ---
And no hold violations either?
If you get a clean bill from TQ and it still fails, then it gets exotic
a) the constraints aren't correct (can't see how, though...)
b) TQ is missing something (very rare but not impossible)
c) the datasheet is wrong
d) the hardware is faulty and doesn't meet the datasheet
At this point, I'd just try to add a bit of safety margin into my constraints and shift the PLL clock a bit more.