How can the universe be a computation?

1. Our best model of the Universal microstructure is in fact a discrete one, and not continuous as you suggest. Everything is quantised, even space and time. Due to quantum uncertainty, distances below the Planck length and time periods shorter than the Planck time cannot occur. The continuous equations which we use to model larger-scale events break down at this smallest scale. Loop quantum gravity is constructed on this principle and is a strong competitor to string theories. It is also worth noting that discrete does not imply binary. Even an analogue computer is discrete in the sense that it resolves down to the nearest quantum of signal energy and no further.
2. and 3. While not all functions can be computed exactly, they can be iterated indefinitely - which is what the Universe appears to be doing. Programming tricks are used to keep diverging functions within manageable limits. (tricks which my first pocket calculator intriguingly lacked). Phenomena such as the uncertainty principle and renormalisation could be examples of such computational tricks.

Posit a sufficiently powerful intelligence with vast resources in a higher-dimensional universe, and why should their unimaginably sophisticated computers not be able to simulate ours? (See at least one other answer)

And there, of course, lies the weakness of the whole naive edifice; despite all the above, your uneasiness is well founded. It is merely dressing up Bishop Berkeley's idealist God in SF technobabble. For "the mind of God" read "a super-alien super-computer". Why bother with the computer? Berkeley's God did not delegate the Creation to the Archangel Gabriel, He just got on with applying Occam's razor, as any good super-alien would do.

It is true that modern information theory is playing an increasingly fundamental role in thermodynamics and cosmology, to the point that at least one respected physicist has remarked that, "The Universe begins to look more like a great thought than a great machine". But to make that leap, and say that the Universe therefore equates to information, begs the question as to why the most complex structures in the Universe (our heads) are so full of illusions, mistakes, paradoxes, contradictions, fantasies and outright lies, yet none of that information manifests itself physically.

Just another example of Einstein's old saw that philosophers may make bad scientists, but scientists make even worse philosophers.

There is a deep philosophical difference between the universe being a computation, and that the universe is computable. There is also an important issue of what model of computation one is assuming: most of the arguments in the question assume discrete Turing machines, but that is of course just one (perhaps obvious) choice.

1: can you make a continuum state machine? Of course! You just have a state transition function like $S_{n+1}=f_1(S_n,I_n)$ where the states $S_n$ and inputs $I_n$ are now members of a set like $R^n$. Don't like discrete steps? Sure, just make it $S'(t)=f_2(S(t),I(t))$. One can obviously embed any discrete state machine in the first equation, and by the right contrived choice of $f_2$ you can embed a discrete step machine $f_1$ in the second equation.

2: You are asserting that the universe realizes all mathematical functions. This is not obviously true and requires a powerful argument.

It is trivial to construct computable functions that cannot be realized in standard physics since there are not enough resources. For example, take the Ackermann function and nest it a bit for good measure: $f(n)=A(A(n+10,n+10))$. Mathematically this is well defined and computable, yet the number of steps to compute $f(1)$ and the amount of information involved vastly exceeds what we think are the bounds on distinguishable bits in the accessible universe and its causal future. If you want to claim it can be computed you need to show how we can get access to computational resources breaking the Bekenstein bound and/or persisting indefinitely far into the future with no error.

3: Physics is not obliged to follow any particular schema. That Lagrangian variational extremisation is hard to compute using our common computers do not mean no computers are good at it (indeed, as quantum computation shows, there exist models of computation that turns problems that are very hard in classical computation feasible), and there is of course no reason to think the universe has to be a perfect Lagrangian mechanics except that so far this model works well. Warton points out that for linking QM to GR you need to use Lagrangian mechanics, but this is based on our current, incomplete understanding of physics: GR, QM and quantum gravity could all work differently from expected and still fit our observations.

I think people underestimate both how weird physics could be and how weird computers could be. While few believe hypercomputation is an actual possibility, we cannot just rule it out a priori. Confidently claiming the universe cannot be computed needs to specify both the computational power of the universe and what computer we speak of. Since that computer doesn't even have to fit into the universe, it is a tall order.