When is $\mathrm{Hom}(A,R) \otimes B =\mathrm{Hom}(A,B)$?

I think I learned something here, so I'll record it as an answer.

Let $R$ be a commutative ring. For an $R$-module $A$, the following are equivalent:
(i) $A$ is finitely generated projective.
(ii) For all $R$-modules $B$ the natural map $\Phi: A^{\vee} \otimes B \rightarrow \operatorname{Hom}(A,B)$ -- i.e., the one induced by $(f,b) \mapsto (a \mapsto f(a)b)$ -- is an isomorphism of $R$-modules.
(iii) The natural map $\Phi: A^{\vee} \otimes A \rightarrow \operatorname{Hom}(A,A)$ is an isomorphism of $R$-modules.

Proof: (i) $\implies$ (ii) is given in Akhil's answer. An (arguably) more purely commutative algebraic proof is given in my comment to his answer. Namely, you have the map $\Phi$ which you want to show is an isomorphism, so it suffices to show that $\Phi_{\mathfrak{p}}$ is an isomorphism for all prime ideals $\mathfrak{p}$ (for this see e.g. $\S 7.7$ of these notes). Since a finitely generated projective module over a local ring is free ($\S 3.5.4$ of the notes), we reduce to the case of $A$ finitely generated and free, and this is easy.

(ii) $\implies$ (iii) is immediate.

(iii) $\implies$ (i): Let $\Phi^{-1}(1_A) = \sum_{i=1}^m f_i \otimes a_i$. Then we have that for all $a \in A$, $a = \sum_{i=1}^m f_i(a) a_i$. By the Dual Basis Lemma ($\S 3.5.3$), this implies that $A$ is finitely generated and projective.

While Mariano has answered the question, and Aaron in the comments has provided a link to a page with a proof, let me briefly note an alternative argument and a slightly tangential philosophical point. Suppose $A$ is finitely generated and projective, and $B$ is any $R$-module. The claim is that $A^* \otimes B \simeq \hom_R(A, B)$ naturally. There is a simple way to see this based on a general observation about functors of $R$-modules.

Namely, suppose $F, F'$ are two functors from the category of $R$-modules to some other category, say an abelian category. Suppose there is a natural transformation $t: F \to F'$ such that $t(M)$ is an isomorphism whenever $M$ is free. Suppose moreover that $t$ is right-exact, i.e. preserves cokernels. Then the claim is that $t(M)$ is an isomorphism for any $M$.

To prove this, consider a free presentation $M' \to M'' \to M \to 0$. Then there is a commutative diagram between the two exact sequences $$ F(M') \to F(M'') \to F(M) \to 0$$ and $$ F'(M') \to F'(M'') \to F'(M) \to 0$$ given by the natural transformation $t$. Since the vertical maps induced by $t$ are isomorphisms on the terms for $M', M''$, it is easy to see (by a diagram chase) that the map $F(M) \to F'(M)$ is an isomorphism as well.

To see how this applies to the present case, fix $A$ projective and finitely generated (so that $A^*$ is easily seen to be finitely generated projective as well, e.g. by dualizing an exact sequence) and note that $B \mapsto A^* \otimes B, B \mapsto \hom(A, B)$ are both right-exact (indeed, exact!) functors because $A^*$ is projective. Since there is clearly a map $A^* \otimes B \to \hom(A, B)$ which is clearly an isomorphism for a free module, the above analysis implies immediately that it is an isomorphism for any $B$.

As a further application of this, you can give a simple proof of the fact that $S^{-1} A \otimes_A M = S^{-1} M$ for any multiplicative subset $S \subset A$. Moreover, the same trick is used to show that for a noetherian ring $A$, $I$-adic completion coincides with tensoring with $\hat{A}$ for finitely generated modules (though it's a slightly different trick because one works with the category of finitely generated $A-modules). One can, in fact, show that any additive functor from $A$-modules to $A$-modules that is right exact and commutes with arbitrary direct sums is given by tensoring with a fixed module*; this is a fun exercise. If one works with contravariant functors, then one sees that a functor from $A$-modules to $A$-modules is representable if and only if it sends colimits to limits. These arguments apply to other categories (which are generated nicely).

Ultimately thinking in this categorical manner is not simply an exercise for its own sake: one situation that frequently arises (e.g. in local duality for local cohomology or in the analysis of the cohomology of the fibers of a coherent sheaf) is that one has a $\delta$-functor from $A$-modules to some abelian category, and one finds that it is identically zero in high dimensions. Then you find from this analysis that the last nonvanishing $\delta$-functor is actually given by tensoring with some module.

*In fact, if $T$ is a functor from $A$-modules to $A$-modules, then if $T$ preserves colimits, $T$ is isomorphic to the functor $M \mapsto T(A) \otimes M$. To do this, one may construct a natural transformation $T(A) \otimes M \to T(M)$ (consider each $m \in M$ as a homomorphism $A \to M$) and then apply the above analysis to this pair of right-exact functors.

In the case you asked about, (with notation switched so that $A$ is a module over the ring $R$) we have the right-exact functor $T: B \mapsto \hom_R(A, B)$, and we want to realize this as a tensor product. The above argument shows that we should take $T(R) = \hom_R(A, R) = R^*$. This in some sense explains the occurrence of the dual object in the above statement.

When $A$ is projective and finitely generated, it works.

If $A$ is free but non-finitely generated, it doesn't; if $A$ is f.g. and non projective, also there are counterexamples.