To answer your question bluntly, yes, the cold can be a concern for standard structural bolts, because the cold can be a concern for just about any metal or plastic. I can give some insight into why the cold is a factor, but I want to be clear that I can't make a recommendation on acceptable temperature ranges for the standard bolts, so if you can't find some data to ensure the proper operation of them, it may be best to use the low-temperature bolts to be safe.
In metals, this phenomenon is known as the ductile-brittle transition, which occurs at a specific temperature based on the material and the strain rate. Note that this means it's dependent on how quickly you deform the material, not how much force you apply.
There are two types of deformation, elastic (where the material returns to its original shape) and plastic (where the material permanently deforms.) On a molecular level, elastic deformation happens when the bonds between molecules in the material are stretched. Because no permanent change in the structure occurs, the material can retain its original shape. At a certain point though, the structure begins to change, often in the form of dislocation movement. Existing defects in the material begin to move, and this movement cannot be spontaneously reversed, causing the permanent change.
The ease and rate of dislocation movement is in part based on temperature. Temperature is a measure of energy, and if there's more energy in a material, some of that energy goes towards dislocation movement. This is important because dislocation motion can help prevent fracture. Cracks exist in all parts, they are impossible to avoid, and parts will fracture at those cracks because stress is concentrated there and the material is naturally weaker.
At these cracks, part of the energy goes into forming new surfaces (propagating the crack further into the part.) Most of the rest of the energy goes into moving the dislocations by plastically deforming the material. If the material is too resistant to deformation (too brittle), no energy will be dissipated by deformation, leaving more energy available for crack propagation. This is what causes metals to be more likely to fracture in lower temperatures. At a certain critical temperature, the material becomes more brittle than ductile, and its fracture toughness is significantly reduced.
Determining this temperature is not simple from a theoretical point, and it's usually done experimentally I believe.
This paper is what I used to refresh my memory from my molecular material behavior class, it's good some good info, but I wouldn't worry about getting bogged down in the math because it's incredibly complex for non-simplified cases. The explanations aren't as bad though.
As I said at the top, the simple answer is yes, it will affect the bolt strength, and I think the standards are reluctant to give specific answers if the bolt isn't designed for a temperature range because bolt size, defect size, and type of loading can all affect this.