But the use of words is nearly always dependent on the context. That's why it's always best to give an example sentence.
For example, if you wanted to buy paper and went into a shop, the assistant is not likely to say the paper's run out, but instead we're out of paper.
You can use more than one tense with out of, e.g. "last week we were out of blue paper".
Time is running out is a standard phrase to say that there is not much time left. There is out of time. We're out of time = There's no time left or (in sport, for example) the end of the game has come. We've run out of timemeans the same.