I would fix the Recovery first, as that's usually the most straightforward. Do you understand what Recovery is? Do you understand why it's failing? Your recovery net should usually be on a global and will meet timing(unless it's a very fast domain). Otherwise you'll need to add registers to meet timing(if it's using local routing).
Once that is fixed, I would look at setup. What's your setup requirement? (.430 isn't too much if you have a 20ns requirement, but if it's 4ns, it's tougher to improve upon). What are your compile times? Are you doing the other options like synthesizing for Speed, turning on Physical Synthesis? How many paths fail?