Of the setup and hold timing constraints which are to be met to get a stable output, which one is critical in estimating the maximum clock frequency of a circuit?
Setup time limits the fastest frequency (shortest period) for the clock. Hold time must be met to have proper operation, and any added buffers or delays to ensure hold time is met can slow the circuit below what you'd estimate from setup time. Beyond this simple rule of thumb, the upper frequency limit depends on the circuit details, and once you determine the critical path you might find ways to improve the design by changing the topology (e.g. put something in parallel, break up the combinational logic across more than one flop in the chain, as in pipelining if added latency is okay).
Another way to think about this: - Setup time relates to behavior from one clock edge to the next and data delay for a change launched on one edge settling before the next clock edge. If you have a setup time violation, you can reduce the clock rate and the circuit will function properly (assuming the clock tree is balanced reasonably well - see Tut's comment below). - Hold time can relate to behavior even on a single clock edge, in the case where a data change on one flop propagates to another flop quickly enough to violate the hold time at the next flop. When this happens the next flop latches the wrong data (the new data instead of the old). Slowing the clock rate will not help a hold time violation. To fix it you must add delay in the violating data path.
The answer to that one is simple: both. If you violate either one you're in trouble. And just using these two will not allow a reliable estimate of maximum clock frequency. You also need, at a minimum, to factor in the propagation delay from clock edge to ouput change. Plus, and this is critical, you need to allow time for propagation of combinatorial delays. Since this is almost always greater than input hold time, you can generally ignore hold time, except in the odd case where you can't.