I know both nonces and timestamps are used to prevent replay attacks, and nonces may offer increased security in the situation a message could be replayed with the timestamp in the allowable window. However, if a nonce can provide all the protection a timestamp does, why would they ever be used together?
However, if a nonce can provide all the protection a timestamp does, why would they ever be used together?
If you use a timestamp in combination with a nonce, it can help mitigate the risk of nonce reuse. Guaranteeing that nonces are never duplicated within the relevant scope can often make a system more complicated, because it needs to maintain state reliably while that scope is "alive."
Imagine, for example, that a system that sends packets encrypted with a counter nonce loses power momentarily, comes back up, and resumes transmission with the key/nonce pair that was saved before the power failed. How do you guarantee that it won't reuse a nonce that it used just before the power loss?
These sorts of problems fall under the rubric of stateful cryptography—cryptographic schemes that require you to keep and update some state between invocations in a correct fashion. Keeping such state incorrectly or unreliably is a common source of failures. Timestamps don't always solve state problems, but they sure can help.
In addition they can be helpful for all sorts of non-cryptographic reasons. For example, timestamps on their own can't generally provide a total order over events because two events may be measured to have happened at the same time. Adding a counter gives you a way of consistently ordering such simultaneous events—even an arbitrary order (that does not reflect reality in any sense) is often useful if all parties agree on it.
If we're talking about replay in particular, if you authenticate the timestamps as associated data and reject data that's tagged too far in the past, you often cut many of the attacker's options, which is generally a plus. But that however doesn't require you to use the timestamp as a nonce for an encryption algorithm, but rather as associated data for authentication.