At what clock frequency do parasitics start to become a problem for digital circuits?
All circuits are inherently analog, even digital ones.  They are all affected by transmission line effects and parasitics.  Whether these effects will be significant or not in how they affect the operation of your circuit is generally dependent on the physical construction and the frequency of operation.  

Parasitics are the 'unwanted' resistance, capacitance, and inductance of the components.  Wires aren't the only source of parasitics, everthing is.  You get capacitors and diodes for free when you build transistors, you get resistors and inductors for free when you build wires, you get capacitors and coupled inductors for free when you put down more than 1 wire, you get capacitors and resistors for free when you build inductors, etc, etc.  In the case of a bread board, the metal clips that hold the wires in are quite large and close to each other, so you end up with a significant amount of capacitance between adjacent rows.  When this will cause trouble is all up to how your circuit is designed and how it operates.  If you're just building digital circuits, you're probably OK up to a few MHz.  But at some point, the coupling from those capacitances is going to couple to an adjacent pin with enough amplitude to affect the operation of the circuit.  When will this occur?  It's hard to say in general with any meaningful precision, but probably somewhere between 1 and 100 MHz.  

Transmission line effects are a slightly different problem, and they come in to play at even higher frequencies.  Transmission line effects result from how electromagnetic waves proagate down wires.  After all, nothing travels faster than the speed of light.  If the wire is long enough that the signal changes faster than it can propagate down the wire, then you have to worry about transmission line effects.  Well, actually the rule of thumb is more like wires longer than 1/10 or 1/16 of a wavelength.  For these cases, you have to use proper RF design techniques (controlled impedance, impedance matching, etc.).  For a proper design, the limit usually ends up being high frequency loss.  Which usually ends up being a few GHz for normal fiberglass/FR4 circuit board.  Faster is possible with better (and more expensive) substrates.