States in C*-algebras and their origin in physics?
I'd like to try to give a more comprehensive answer.
In the elementary formulation of quantum mechanics, pure states are represented by unit vectors in a complex Hilbert space $H$ and observables are represented by unbounded self-adjoint operators on $H$. The expected value of a measurement of the observable $A$ in the state $v$ is $\langle Av,v\rangle$. We could also say that the state is represented by the linear functional $A \mapsto \langle Av,v\rangle$, and this interpretation generalizes to say that a mixed state is represented by a linear functional $A \mapsto {\rm Tr}(AB)$ where $B$ is a positive trace-class operator satisfying ${\rm Tr}(B) = 1$.
The fact that $A$ can be unbounded is forced on us by basic physical examples like position and momentum. Mathematically, it is easier to work with bounded observables, which can be obtained from unbounded observables via functional calculus: if $f: \mathbb{R} \to \mathbb{R}$ is bounded and measurable then we can give meaning to $f(A)$ as a bounded self-adjoint operator.
In the C*-algebra formulation, bounded observables are self-adjoint elements of a C*-algebra $\mathcal{A}$ and mixed states are positive linear functionals on $\mathcal{A}$ of norm one. The pure states are the extreme points of the set of mixed states.
We can always pass from the C*-algebra formulation to the elementary formulation using the GNS construction: given a state $\phi$ on a C*-algebra $\mathcal{A}$, we can find a Hilbert space $H$, a $*$-representation $\pi: \mathcal{A} \to B(H)$, and a unit vector $v \in H$ such that $\phi(x) = \langle \pi(x)v,v\rangle$ for all $x \in \mathcal{A}$.
Why bother with the C*-algebra formulation, then? Well, maybe you don't need to. But sometimes there are good reasons for looking at things this way.
Superselection sectors. A characteristic feature of quantum mechanical states is that they can be superposed. Schrodinger's cat can be alive, dead, or in some combination of the two states. But there may also be general principles which prevent certain states from being combined in this way. In elementary quantum mechanics, particle number is an unchangable quantity: an isolated system couldn't be partly in a state with one particle and partly in a state with two particles. We could tell how many particles there are in the system without measuring it, by counting how many particles are outside and subtracting this from the total number of particles in the universe. Similarly for charge. (Emphasize: I'm talking about elementary QM now.) Quantities like this produce "superselection sectors", orthogonal subspaces of $H$ which cannot be superposed. This means that certain observables are forbidden. In elementary quantum mechanics you could not have an observable with the property that the result of a measurement could be a state with an indeterminate number of particles. The mathematical condition is that every physical observable has to commute with the observable $N$ which measures the number of particles in the system. The relevant C*-algebra would not be all of $B(H)$, but only the set of operators which commute with some special family of observables (particle number, total charge, etc.)
I put this example first because it applies even to the nonrelativistic, finite particle case that the OP cares about, at least if one wants to model a variable number of particles, say.Thermodynamic states. In quantum statistical mechanics, the physical description of a system can involve macroscopic parameters like temperature which correspond to inequivalent states on the observable C*-algebra. This means that the GNS representations corresponding to one of these states does not include the other state as a unit vector or even a trace class operator (density matrix). The Hilbert space formalism simply models different temperatures with different Hilbert spaces. In some sense this formalism still works, but it does not capture the idea that the same physical system can have different temperatures. The C*-algebra formalism does capture this aspect, because it is the same C*-algebra (a CAR or CCR algebra), being represented in different ways on different Hilbert spaces.
Free fields in curved spacetime. We do not have a good mathematical theory of quantum mechanics plus general relativity, but we do have a good understanding of noninteracting quantum fields against a curved spacetime background. Phenomena like Hawking radiation can be understood rigorously in such a way, for instance. What happens here is that a single physical state may be perceived in radically different ways by different observers. In Minkowski spacetime, for instance, a ground state with no particles according to an inertial observer will be seen by a uniformly accelerating observer as a "thermal bath" of infinitely many particles --- a thermodynamic state of the type discussed in point 2. In this case there is a preferred reference frame, the inertial frame, but in general relativity there is no preferred frame. But, wonderfully, that there is a single C*-algebra (again CAR or CCR) that captures the observables for all observers and all states. The elementary Hilbert space formalism is really inadequate in this case.
1.) Yes. In the commutative case, this is the statement of the Riesz representation theorem (any linear functional on $C(K)$ is an integral against a measure, which has to be positive by the positivity condition on the state).
In the non-commutative case, the answer may be Yes or No, depending on how you phrase the question. As pointed out in the comments, there may be states $\langle - \rangle$ on $L(H)$ that are not of the form $\operatorname{tr}(\rho(-))$ for a trace-class $\rho$. However, the GNS theorem states that any state gives rise to a representation $\pi$ of $L(H)$ by bounded operators on a possibly different Hilbert space $H'$ such that the state is in fact of the form $\operatorname{tr}(\rho \pi(-))$ for some trace-class (in fact rank-1) $\rho$. Of course, the representation $\pi\colon L(H) \to L(H')$ on $H'$ may not be unitarily equivalent to the defining representation $\mathrm{id}\colon L(H) \to L(H)$ on $H$.
2.) This question is rather subjective, so it is impossible to answer with mathematical precision. Both classical and quantum mechanics came first, along with their own motivations, and the $C^*$-algebraic descriptions were later noticed and retrofitted onto the theories. One thing that can be said is the following. Thinking carefully about taking the classical limit of a quantum system, one can recover from a non-commutative algebra a commutative one with a Poisson bracket. Naturally one can also ask whether a non-commutative algebra can be obtained from a commutative one with a Poisson bracket. Such things are studied under the name deformation quantization.