Is the universe's Kolmogorov complexity growing over time? The Kolmogorov complexity of a deterministic universe is constant.
The Kolmogorov complexity of a nondeterministic universe grows over time. It grows whenever something happens that is not predetermined by its laws of nature. E.g. randomness or free will.
Would it be possible to measure a difference? If the universe's information content grows, does that also increase its energy content?
Edit: By "complexity of a universe" I mean the amount of information required to simulate it up to some point in time.
 A: There are several reasons why this question doesn't make sense:
Algorithmic complexity is relative to some language, but you haven't specified one.
The universe is probably infinite, so its information content may be infinite.
The universe is not a classical system, so classical bits aren't a good way of measuring its information content. Qubits would make more sense. For a quantum system, we expect its information content to stay constant, because time evolution is unitary.
A: 
Would it be possible to measure a difference?

No, if we are talking about the universe in which we live, and not some simple abstract universe. Why not? Because it's really hard to distinguish a good deterministic pseudo-random number generating algorithm from true randomness. And given that we can access only a minuscule portion of the information describing the universe, this task becomes impossible.

If the universe's information content grows, does that also increase its energy content?

No, there is no relation.
