What is a completely positive map *physically*?

Physically, a CP map represents evolution processes even in the presence of entanglement.

After all positive maps sends a state to a state

This is false when the system is entangled with something else. The classic example is the transpose on the system of interest. (Technically, a transpose, since it's basis-dependent.) Since positivity can be characterized using determinants, transposing preserves positivity. However, if you only transpose a tensor half of a big matrix then this fails. Again, the standard example is a pair of qubits entangled in the $|\phi^+\rangle={1\over\sqrt{2}}\left(|00\rangle+|11\rangle\right)$ Bell state. Then the total density matrix is

$$\rho=\frac{1}{2}\begin{pmatrix}1&0&0&1\\0&0&0&0\\0&0&0&0\\1&0&0&1\end{pmatrix}$$

and when transposed over the second qubit (done transposing each of the four submatrices) it goes to

$$\rho^{T_\textrm{B}}=\frac{1}{2}\begin{pmatrix}1&0&0&0\\0&0&1&0\\0&1&0&0\\0&0&0&1\end{pmatrix},$$

which is not positive ($(0,1,-1,0)$ has eigenvalue -1).

That's the math. The physics it implies is that while you can ensure lone-system positivity of a map with purely local conditions, it does not imply that it works as a physical evolution for a larger, entangled system.

Physically, a completely positive map is just the kind of transformation one can achieve by passing a beam in a certain mixed state through some device (the transformer) thereby producing another beam in a usually different mixed state, allowing for dissipative effects.

Clearly, such a transformation must map states into states and hence be positive. But under the standard asssumptions of a unitary dynamics of the universe as a whole, it is a restriction of a unitary map of the bigger system consisting of beam plus transformer. This implies that it has the form given in Stinespring's theorem, and is therefore completely positive.

Conversely, Stinespring's theorem says that each completely positive map can be realized as the restriction of such a unitary dynamics, hence is (in principle at least) experimentally realizable.

Completely positive maps can be characterized without involving external systems by means of the Stinespring factorization theorem, which reduces to Choi's theorem for the case of finite dimensional Hilbert spaces:

$ \Phi(a) = \sum_{i=1}^{mn}V_i^\dagger a V_i$.

Completely positive maps are considered to represent the most general quantum evolutions, however, Shaji and Sudarshan in Who’s afraid of not completely positive maps? gave arguments that they do not exhaust all physical evolution possibilities.