I just picked up a vintage 300mm bellows with a 50mm lens on the M42 screw mount, but the lens is kinda foggy and scratched. What would I gain or lose with different focal lengths for a replacement lens?
Assuming your bellows just allows extension, and does not offer tilt or shift capabilities...then that's all you really get, extension. If your bellows is a full-freedom bellows with tilt and shift (and maybe even rotation) capabilities, then the answer to your question is probably more complex.
With greater extension (elongation of the bellows), you reduce the minimum focus distance of whatever lens is attached. Exactly what that means really depends on the lens. Lenses of the same focal length but different design can have different MFDs, so exactly how much extension you can handle before the focal plane ends up inside the lens really depends. I wouldn't say there is anything special about a 50mm lens, nor shorter or longer lenses.
If your bellows is more capable, then you have to think about more things. Tilt and shift capabilities, while they can be useful for macro to a small degree, put a lot more demand on the lens. You need a larger image circle, so that when you move the bellows, you don't end up vignetting the sensor. Most DSLR/Mirrorless lenses these days have fairly constricted image circles, without much in the way of freedom. You may find that older vintage lenses, especially medium and large format lenses, may offer a LOT more in the way of working image circle for use with a full-freedom bellows. These lenses can be expensive, but they can often handle up to 25° of tilt, where as DSLR/mirrorless lenses may barely be able to handle about 8° at most (given their smaller image circles). At 8° you might not see much in the way of benefit for macro (the distances involved don't lend themselves well to the Scheimpflug principal), however at up to 25° of tilt you might start to see some useful benefit at macro scales.
Different focal lengths will give you more or less working room. The longer the focal length, the further you can be from your subject.
Another alternative is to use old enlarger lenses, with an appropriate step up ring to get to M42 size. They actually work extremely well for macro photography, and they have no focusing helicoid, so they are made for a bellows. Some very good enlarger lenses are Schneider-Kreuznach, Fujinon, Rodenstock, and EL-Nikkor. A 50mm or 70mm would work fine. You should be able to find them for less than $50 each, and their quality is stellar.