Can we construct a UTXO which is spendable only via proof of work? Do the current Bitcoin opcodes and transaction size limit allow constructing a UTXO which is only spendable if a specified amount of work has been performed? 

So the spender, would provide a nonce as input to the script. Then the script would essentially perform a highly simplified version of how bitcoin's block headers are verified (the nonce is combined with some other data, hashed, and the hash is compared with a "target.").

Without OP_CAT and with arithmetic limited to 4 byte inputs, do I understand correctly that the above would be impossible? Or is there some workaround?
The answer depends on what you are trying to accomplish with this construction. I have three guesses in this regard:

a set of determined recipients can spend if they perform the PoW: you can have a transaction that can be spent if someone provides: a value whose hash is less than a specified amount (that determines difficulty) AND a signature that describes the set of allowed entities (potentially any multisig).
anybody that performs the proof of work can spend (AND you can spend without PoW): this is trickier since a simple hash based PoW would not work, a miner can just change the destination address of the spending transaction to one under his control. You need to prove that you know a secret (the result of the PoW) without actually including it in the tx so that miners are not able to take the money without repeating the PoW: this is what digital signatures accomplish. As suggested in the comments you can contsruct a utxo that can be spent by signing with a certain private key known by you alone and that contains part of it under an op_return. So one has to try any private key in the set of the allowed ones until he can produce a valid signature. This does not leak the private key itself so the miner cannot sign the same tx with a different destination address.
anybody that performs the proof of work can spend (AND you can NOT spend without PoW): I thought about this a while and I can't find an easy construction for this, it might be hard even with stronger scripting capabilities than bitcoin's. My best guess is that you have a provably random public key (for instance using a VDF on the nonce of the last block) and everybody has to brute-force the private key to spend. I see two major issues: miners can have some advantage in selecting nonces to influence the randomness of the PK and it's hard to tune the difficulty, you need a custom signature scheme that has the security level you want and that's not trivial with bitcoin script.

This is NOT a complete list, it's just the first ideas that came to my mind. Especially the second case, which looks the most likely to me, can be constructed in several different ways: for instance you could also publish the hash of the private key in an op_return (so the private key doesn't have to be included in the transaction) and you would turn it into a hash-based PoW since hashing is a lot faster than signing.