Feeling of powerlessness - tiring.
Fear of suffering if you choose wrong (plus bonus regret), inability to gather info enough to ensure outcome - tiring.
Feeling of scarcity - that you can't just lock in some "if it turns out I'm wrong, I win anyway, I have this insurance ..." security, but instead must really bear an emotionally crushing loss - tiring.
Is an omnipotent omniscient tired out by decisions? No.
Okay, but then why are those things tiring? These all seems to be forms of failing to meet expectations (e.g. you expected to have more power and failed to have it, else you wouldn't feel powerless just observe you are without power), so maybe it's something to do with that? But why would that be a tiring experience or otherwise wear you down? Does it involve the expenditure of some scarce neurological resource?
One notable aspect in my experience with this is that exhaustion is not exclusively a function of the decision's complexity. I can experience exhaustion when deciding what to eat for dinner, for instance, even though I've made similar decisions literally thousands of times before, the answer is always obvious (cook stuff I have at home or order from a restaurant I like - what else is there?), and the stakes are low ("had I given it more thought, I would have realize I was more in the mood for soup than a sandwich" is not exactly a harrowing loss).
Another aspect to note is that decisions that end up exhausting me usually entail doing work I don't want to do. I never get exhausted when deciding where to hike, for instance, because no matter what I know I will enjoy myself, even if one spot requires a long drive, or inconvenient preparations, or whatever. One possibility is that part of me recognizes that the correct decision will inevitably cause me to do work I don't want to do. Actually deciding sets whatever work I have to do into motion while "deliberating" endlessly lets me put it off, which might end up feeling internally like the decision is hard to make. A motivated mind is great at coming up with bogus reasons for why an obvious decision is not so obvious.
A key insight for me was recognizing that my reluctance to do work is pretty directly proportional to what I expect the value of its product to be, biased towards short term gains unless I explicitly visualize the long term consequences. If realizing that the best decision for dinner is to cook, and that reminds me that I need to do dishes and chop vegetables and clean the stove, etc. etc. then I have a hard time "deciding" that cooking is the way to go because it implies that in the short term, I will be less happy than I am currently. If I think about the scenario where I procrastinate and don't cook, and focus on how hungry I will be and how unpleasant that feeling is, then my exhaustion often fades and the decision becomes clearer.
Speculation based on my experience with and research on the sorts of transformations that spiritual practice and psychedelics sometimes facilitate:
This has to do with our sense of meaning and fittedness-for-purpose of our mental frameworks. When we try to go against these, we expend willpower and become fatigued. When the task is meaningful to us and fits well with our frameworks, we engage effortlessly, like water flowing downhill.
I've had major transformations that exhibit this pattern: some previously interesting activities become dull and boring, and some new activities become meaningful and interesting. If I try to persist in the old activities, I quickly become fatigued and lose interest. Once I switch to the new activities, I can spend hours with effortless focus. Sometimes I'd had prior experience with the "new" activities and found them boring at the time.
Many people experience something we might call decision or executive exhaustion: after making a lot of decisions, it can be hard to make more decisions and to exert "willpower". Yet, this seems odd because we are constantly making decisions all the time in some sense, choosing to do what we do over everything else we could have otherwise done. So, what and why do we sometimes get exhausted of making decisions when most of the time we do not?
Some notes to consider in answering: