Paul was exhibiting some latent abilities, such as dreaming of his future encounter with Chani, and some not so latent ones, such as his predisposition to mentat awareness, while still on Caladan. He would have encountered some Spice as party of his diet already, though.
On Dune, he was constantly exposed to the Spice, but it would seem to have only enhanced his abilities by small degree.
The crucial point at which he becomes the Kwisatz Haderach is when he drinks of the Water of Life. This is used by the wild Reverend Mothers of the Fremen, the Sayyadina, to unlock their own powers. The Bene Gesserit simply use a different substance to achieve the same effect - and probably planned on having Paul go through the same trial.
(I'll spoiler this in case you have yet to read the sequels)
Note that in Children of Dune, while Leto II is pre-born as is his sister, it is only after Leto is overdosed on Spice that he too becomes a fully fledged Kwisatz Haderach - he does not need the Water of Life. His next step was to enter symbiosis with sandtrout - but that is not part of the Bene Gesserit plan.
So, as far as the Bene Gesserit plan to produce a Kwisatz Haderach who could survive the Spice Agony - there's nothing to say that Paul (or the intended grandson of Jessica) could not have done this away from Arrakis, and so we cannot say it was doomed to fail on that count.
The other part of the plan was to have a Kwisatz Haderach under the control of the Bene Gesserit. Paul very much is under no one's control. On the other hand, the Sisterhood did not expect Paul to be a Kwisatz Haderach. Had Jessica had a daughter, and she in turn had a son, the Sisterhood may well have taken a more active role in the education and indoctrination of the child.
