According to the HP 3456A's parts list, CR6,8,9,10 are part number 1920-0028 which are 400V, 0.75A general purpose diodes. You could replace them with 1N4004 diodes. The 1N4001 you suggest is only rated to 50V reverse voltage, so why take a chance when the 1N4004 has the correct rating and the parts are so inexpensive and readily available.
Also, CR7 is an 18V, 5 watt Zener diode, 1N5355B. It should not be replaced by a 1N4004. While that won't hurt anything, you would lose the overvoltage protection that the Zener is providing.
But the bigger question is why are you replacing these diodes (and electrolytics)? Is the power supply malfunctioning? If the supply is working, I would leave the thing alone. Unless you see 120 Hz ripple on the power rails, or there is obvious capacitor bulging or leakage, I wouldn't fuss with it. And diodes heating and discoloring boards is quite commonplace. You could lift them 1/8" off the board if it upsets you.
A preemptive replacement of the line filter is a toss-up. These things seem to be more problematic when using 240 VAC, not 120 VAC as the input voltage. But they do make a mess if and when they explode. And you are quite correct that if you ever find any of the gold-colored RIFA suppression caps, they should be replaced immediately without question.