As you said it would create a paradox, because with the past changed Odine couldn't know to destroy the machine and therefore wouldn't. In theory he could start a parallel timeline containing people from an alternate (the original) future and still get rid of the machine. But that wouldn't solve the problem and is only possible if time travel works like that.
Time travel in VIII doesn't really work with any kind of logic so it's best to just roll with it.