The discovery that made nuclear weapons possible was the nuclear fission chain reaction, which is one step further than nuclear fission itself, but not much of a step further. An individual fission reaction releases a lot of energy for an atomic-scale reaction, but so do all nuclear reactions. What makes fission special is that in certain isotopes (defined as "fissile"), the neutrons that also get released from the reaction can go on to start multiple new reactions under the right circumstances. So if you have a lot of these fissile atoms together in the right way, you can get a rapidly exponential chain reaction that releases a lot of energy. This is different than nuclear reactions already known to scientists in the 1930s, which also released a lot of energy (hence there was a large pre-fission discourse about "atomic energy") but couldn't be made to release it in a controlled and macroscopic way.
When you do the math as to "how much energy," the answer is pretty profound:
Each U-235 fission reaction releases ~200 MeV of energy (this is easy to calculate using E=mc^2 or by looking at the Coulomb repulsion of the fission fragments)
There are ~2.56e+24 atoms of U-235 in a kilogram (just an application of Avogadro's number)
2.56e+24 * 200 MeV = 8.2e+13 J = ~20,000 tons of TNT
So scientists looked at this and said, oh boy, that's a lot of energy to get out of something that weighs 1 kg (2.2 lbs). You can also figure out that since each reaction takes a certain (small) amount of time (a few nanoseconds), you could imagine making a trillion trillion (not a typo) atoms fission in less than a millisecond if you did it right.
That doesn't mean they all immediately agreed it was practicably feasible. That's a big step into a different direction, and in the end only the British initially believed this, and they convinced the United States it was true and that (eventually) launched the Manhattan Project (in 1942). The other nations on your list all concluded that it was theoretically possible but not something they could afford to risk working on during the constraints of the war.
The practical questions are things like:
\1. Your material is not going to fission 100%. How much material do you actually need to get 1 kg of fissioning under a given set of circumstances (e.g., bomb design)? The answer to this varied quite a bit; it turned out to be 64 kg of U-235 for one kind of bomb, and 6.2 kg of Pu-239 (a man-made isotope) for another.
\2. How do you practically make these fissile isotopes? This turned out to be the biggest expense of the Manhattan Project, separating U-235 from the more common U-238, and making industrial-sized nuclear reactors to produce Pu-239 from U-238.
\3. How do you create the circumstances — the bomb design — for making sure this reaction will proceed as desired and not just either destroy itself before it really gets going? This turned out to be fairly difficult for the Pu-239 weapon (not the U-235 bomb), because reactor-bred Pu-239 had impurities that made it not very amenable to use in a simple design, and a far more complicated (if more efficient) design had to be developed.
And there were multitudes of uncertainty about every aspect of the theory of this that had to be nailed down to real numbers in order to translate the vague idea of an atomic bomb into an engineered, usable reality. I'm glossing over their level of knowledge in the early days here just to make a point; they needed to really understand the theory of fission, for example, to know that U-235 was going to be fissile and U-238 was not going to be, and that wasn't obvious at the immediate onset of this discovery (but was known by the end of 1939). Richard Rhodes' The Making of the Atomic Bomb goes into a lot of detail as to what they knew at what point.
So what I would say is that the discovery of nuclear fission and the idea of the fission chain reaction certainly pointed to the possibility that atomic bombs could be built. But confirming that this possibility was real, much less doing it, took a lot more work. Only with the detonation of an atomic bomb over Hiroshima did the possibility of an atomic bomb turn into a firm reality for, say, the Japanese and the Germans. (For the Americans, UK, and Soviets, it was a bit earlier than that — at least the Trinity test, but arguably a bit earlier because of all of the experimental work being done. The US and UK were working together; the Soviets knew about their work through espionage.)