Yes, that should work well. You might consider also looking at our clear-lens yellow flickering LEDs, which are particularly good for this purpose, since they project more of a beam than the diffused LEDs in the flickery flame kits.
Computer fans are not particularly tolerant of unexpected voltage inputs– a 5 V DC computer fan wants steady 5 V DC. Using a regulator is an OK idea, but it might be better to give it 6 V DC (4 C or D cells), with a load resistor and/or diode to drop the voltage down to 5.
