Taking hidden variables to mean an underlying dynamics characterised by some hidden variable $\lambda$, which characterises a definite state of a system at any given time, whilst reproducing the statistical predictions of a quantum mechanics. Since such a model is, by construction, classical does that necessarily mean problems that are soluble by a quantum computer in polynomial time would, in practice, have a large complexity should Hidden-Variables be true as it cannot take advantage of superposition and interference? For example should a large scale quantum computer be developed, tasked, using Shor's algorithm, with factorising large primes actually find the problem as difficult as a classical computer?
It depends what you define as a computation. It will certainly not work as Turing machine (or a modern computer), because a Turing machine is local, in the same way that a cellular automata. If you define a cellular automaton with nonlocal rules, then it will be much faster than a turing machine, in the sense that many NP problems will become polynomial in time. I do not think the speed up is specific to QM, but to many other non-local rules too.
For instance, you can define quantum cellular automata that do have an exponential speed up. But even if they claim to have local rules, the computation is nonlocal: because of the conservation of the total probability for each time step, information of the global array spread out over generally nonlocal distances must be conveyed for each time step to each local site via the normalization procedure (see here).
I do not have knowledge of non-local cellular automata that could have more power than a Turing machine (not just a speedup), but I would not be surprised if somebody finds one (well, perhaps there is some theorem that does not allow it). Other extensions of Turing machines, local but that can run on ordinal time do have super Turing power.
I wonder if a cellular automata based on Newtonian mechanics could result in exponential speedups due to the fact that Newtonian mechanics is nonlocal (my guess is no, but I hope somebody here knows better).