If the universe were predetermined, would non-deterministic automata still make sense?
It makes perfect sense. Non-deterministic automata and non-deterministic algorithms in general are useful in many situations. The best known situation is when one designs algorithms (or strategies or recipes or ..) and analyzes them. 

For example, an algorithm for computing the maximum element of a set of numbers will have a loop of the form "as long as the set is not empty, take out an element and compare it with the current max value". This algorithm is non-deterministic because I did not explain how one chooses what element to pick. I did not explain it because it is not important for the correctness of the method (and because deciding in advance how to pick an element would blur the issues and limit the scope of my algorithm). 

Note that, in all likelihood, all actual implementations of the algorithm will run deterministic code. But it is useful for me to think in term of the more abstract, more generic, non-deterministic algorithms. You may give it a different name but non-determinism is an essential concept.

Here is another way to see that non-determinism in mathematical models is not related to non-determinism in the actual world : your question is similar to me asking if the universe is governed by predeterminism, does the $P\not=NP$ question make sense?