Both are fully correct.
fully = completely, utterly. Period.
Fully exhausted only appears a bit odd to the eye if one suddenly sees it in a literal sense and imagines something being "full" as opposed to "empty".
One can say fully exhausted, fully refreshed, fully rested, fully satisfied, fully spent, but not usually fully tired or completely tired because the tendency is to use a much stronger adjective with fully, which is a superlative adverb.
I was somewhat (quite, very, extremely) tired by the time we arrived.
I was fully (completely, utterly) spent (wrecked, done in, exhausted) by the time we arrived.
The converse is also true. If one uses a weaker adverb or adverbial phrase, one wouldn't usually use a superlative adjective, but rather a less strong one:
I was slightly (somewhat, just a bit) tired by the the time we arrived.
Only with a degree of intentional humo(u)r would one say:
I was somewhat (ever so slightly, a wee bit) wrecked (done in, shot, spent) by the time we arrived.