How to perform circuit calculations for the darlington pair

Yes, that's essentially correct.

However, you should actually over-drive the base of the transistor in order to make sure that it stays in saturation even if conditions change a bit (particularly transistor current transfer ratio, which is difficult to control precisely). This is called a "design margin".

So, assume that in the worst case, the h_FE of your transistor is 1/2 or even 1/3 the "nominal" value, and redo your resistor calculation accordingly. There's no harm in introducing more current than needed (within limits, of course) to the base of a transistor.

I'm assuming your circuit looks like

^{simulate this circuit – Schematic created using CircuitLab}

Assuming this is true, I think you're running up against a characteristic of the Darlington - high saturation voltage. In this configuration, the high gain does not carry over to the situation where you want to turn the transistor hard on. Instead of a transistor voltage of ~0.2 volts, something like 0.8 is more likely. This means that the relay is only getting about 4.2 volts, and this is close to the operating limit. As a result, you have to drive the Darlington harder than you think you need to.

Instead, try this:

^{simulate this circuit}

This will allow more voltage across the relay.

In any event, compound transistor connections aren't magic. The problem is that at the very low current levels you expect with the first stage, current gain goes way down, so the overall gain is less than you expect from reading the data sheet.

Also note the catch diode. Always use one of these. If you don't, you'll get a turn-off voltage spike which may well kill your transistor.