Is cellular for Apple Watch ever available for a pre-paid phone plan?
There is no technical constraint preventing an Apple Watch cellular from being used with a pre-paid plan.
I have used an Apple Watch Cellular with pre-paid plan in India.