I also think that setup is the deciding factor in the digital circuit, as there are some cases when the hold violations are being fixed after place&route phase of the design.
setup is deciding factor for "calculating max frequency". The design wont work properly if you have setup or hold violations on the path. But you can avoid the setup voilation by operating at a lower frequency which is not possible in the case of hold violations.
Agree with chipmonkey. By decreasing the frequency the hold violation still remains. But on the other hand usually the hold violations are being fixed after p&r phase.