The choice of a map $k$ is equivalent to that of a map $k':X\to X^{**}$ satisfying $ k'(x)(y^*)=k(x,y^*)\qquad\text{for all }x\in X, y^*\in X^*. $ One has a natural injective map $\iota:X\to X^{**}$ given by $\iota(x)(y^*)=y^*(x)$. The requirement for you map $f$ can now be expressed as $ k'(x)(y^*)=\iota(f(x))(y^*)\qquad\text{for all }x\in X, y^*\in X^*, $ which means $\iota(f(x))=k'(x)$ for all $x\in X$, or simply $\iota\circ f=k'$. It can be seen that this is possible if and only the image of $k'$ is contained in that of $\iota$ (in which case one can take $f$ to map any $x$ to the unique $x'\in X$ with $\iota(x')=k'(x)$). Since $k'$ is arbitrary in the question, one cannot guarantee this unless $\iota$ is surjective (hence bijective). Now this is known to be true if and only if $X$ is finite dimensional, so the answer to your question is that only with this additional hypothesis a proof can be given (and the choice of $f$ can be expressed as $f=\iota^{-1}\circ k'$ in this case). In the infinite dimensional case, you can easily give a counterexample once you are given an element of $X^{**}\setminus\iota(X)$, which exists for dimension reasons but may be hard to actually find.