Can any computational challenge be transformed to proof-of-work?
(Note:  Andreas Björklund suggested a solution in the comments that I believe is better than the one described below. See http://eprint.iacr.org/2017/203, by Ball, Rosen, Sabin, and Vasudevan. In short, they give proofs of work based on problems like Orthogonal Vectors whose hardness is well understood and to which many problems (e.g., k-SAT) can be reduced relatively efficiently. Their PoW instance $\Psi(\mathcal{C})$ is as hard as a worst-case Orthogonal Vectors, even if the input instance $\mathcal{C}$ is easy, so that they avoid a major drawback of the solution described below.

The solution described below might benefit from its simplicity---it can be described to a non-expert---but it seems to me to be much less interesting theoretically.)

A solution is possible if one makes the strong assumption that "the fastest algorithm for $\mathcal{C}$ is fundamentally randomized" (and if we model a cryptographic hash function as a random oracle). One way to formalize this is to say that 


$\mathcal{C} \in \mathsf{TFNP} \setminus \mathsf{FP}$ (otherwise, I guess it's not really a valid challenge); 
the fastest randomized algorithm for $\mathcal{C}$ runs in expected time $T$ on a typical instance; and 
there exists an efficiently computable function $f$ from $\{0,1\}^k$ to the domain of solutions to $\mathcal{C}$ for $k \approx \log_2 T$ such that there always exists an $s \in \{0,1\}^k$ with $f(s)$ a solution to $\mathcal{C}$.


Notice that the assumption that $k \approx \log_2 T$ implies that brute-force search of $\{0,1\}^k$ is essentially the optimal algorithm for $\mathcal{C}$. So, this is quite a strong assumption. On the other hand, if $\mathcal{C}$ does not satisfy these properties, then it's hard for me to imagine satisfying both your conditions (2) and (4). 

Then, given a hash function $H : \{0,1\}^* \to \{0,1\}^k$, which we model as a random oracle, we define $\Psi_H(\mathcal{C}; r)$ as follows, where $r \in \{0,1\}^\ell$ for some $\ell \gg k$ is the random input to $\Psi_H$. The goal is to output $x \in \{0,1\}^*$ such that $f(H(r,x))$ is a solution to $\mathcal{C}$. In other words, $(r,x)$ should hash to "good random coins" for the above algorithm.

Let's see that this satisfies all of your conditions.


"The function $\Psi$ is randomized, using some (public) random sequence $r$." Check!
"Solving $\Psi(\mathcal{C})$ is typically as hard as solving $\mathcal{C}$." Notice that the simple randomized algorithm for $\Psi_H(\mathcal{C},r)$ runs in expected time at most $2^k$ plus polynomial overhead, and by assumption $2^k \approx T$ is essentially the running time of the optimal algorithm for $\mathcal{C}$.
"If a solution $x$ is found for $\Psi(\mathcal{C})$, then a solution $\Psi^{-1}(x)$ can be efficiently computed for the original challenge $\mathcal{C}$." This can be done by computing $f(H(r,x))$, which is a solution to $\mathcal{C}$ by assumption.
"Knowing a solution for $\mathcal{C}$ does not help in finding a solution for $\Psi(\mathcal{C})$." By definition, solving $\Psi_H(\mathcal{C}; r)$ requires finding $x$ such that $f(H(r,x))$ is a solution to $\mathcal{C}$. Since we modeled $H$ as a random oracle, we can lower bound the expected running time of any algorithm that solves this problem by the optimal expected query complexity of the query problem in which $H$ is given by a black box and we are asked to find a solution to the same problem. And, again because $H$ is a random oracle, the expected query complexity is just the inverse of the fraction of elements $x \in \{0,1\}^k$ that are solutions (up to a constant factor). By assumption, the optimal expected running time of any algorithm for $\mathcal{C}$ is $T \approx 2^{k}$, which implies that this fraction cannot be much larger than $2^{-k}$. Since $\ell \gg k$ and $r \in \{0,1\}^\ell$ is chosen uniformly at random, this is even true with preprocessing that is allowed to depend on $H$ and $\mathcal{C}$ (but not $r$), and in particular it is true even if we know a solution to $\mathcal{C}$ in advance.