It doesn’t resemble the computers of today, but none the less it was indeed a stored program digital computer. The first of its kind. The bombes were more akin to a special purpose calculation machine. Colossus was something a bit more special.

‘Stored program’ is where the debate is. Colossus was ‘programmable’ but the program was not a series of instructions executed in a sequence - it was a single data process executed on the input data against a set of stored registers.

Definitely programmable, definitely capable of computing, but not a ‘stored program’ in the sense we know it today.

Having seen the replica, I noticed it has a long continuous tape loop. Was the program "stored" in the paper tape?

That was the data. Point of Collosus was to analyze ciphertexts; the text goes on the loop. It’s looped so your program can run over the data multiple times, since it’s sequential access only.

It was the first programmable electronic digital computing machine, yes. Special-purpose computing machines had been around since the 1600's (where they were used as textile weaving machines I think).

And the “electronic” part is important. The Z3 predates in by 2 years and was a programmable digital computer, except it used electromechanical relays.

The Z3 is arguably more programmable than colossus and it was proven to be Turing complete in its stock configuration. Though the Z3 lacked the ability to conditionally branch, so nobody realised it at the time.