I don't think I can really give you the intuition that you seek because I don't think I quite have it yet either. But I think that understanding the relevance of Nigel Higson's comment might help, and I can try to provide some insight. (Full disclosure: most of my understanding of these matters has been heavily influenced by Nigel Higson and John Roe).
My first comment is that the index theorem should be regarded as a statement about K-theory, not as a cohomological formula. Understanding the theorem in this way suppresses many complications (such as the confusing appearance of the Todd class!) and lends itself most readily to generalization. Moreover the K-theory proof of the index theorem parallels the "extrinsic" proof of the Gauss Bonnet theorem, making the result seem a little more natural. The appearance of the Chern character and Todd class are explained in this context by the observations that the Chern character maps K-theory (vector bundles) to cohomology (differential forms) and that the Todd class measures the difference between the Thom isomorphism in K-theory and the Thom isomorphism in cohomology. I unfortunately can't give you any better intuition for the latter statement than what can be obtained by looking at Atiyah and Singer's proof, but in any event my point is that the Todd class arises because we are trying to convert what ought to be a K-theory statement into a cohomological statement, not for a reason that is truly intrinsic to the index theorem.
Before I elaborate on the K-theory proof, I want to comment that there is also a local proof of the index theorem which relies on detailed asymptotic analysis of the heat equation associated to a Dirac operator. This is analogous to certain intrinsic proofs of the Gauss-Bonnet theorem, but according to my understanding the argument doesn't provide the same kind of intuition that the K-theory argument does. The basic strategy of the local argument, as simplified by Getzler, is to invent a symbolic calculus for the Dirac operator which reduces the theorem to a computation with a specific example. This example is a version of the quantum-mechanical harmonic oscillator operator, and a coordinate calculation directly produces the $\hat{A}$ genus (the appropriate "right-hand side" of the index theorem for the Dirac operator). There are some slightly more conceptual versions of this proof, but none that I have seen REALLY explain the geometric meaning of the $\hat{A}$ genus.
So let's look at the K-theory argument. The first step is to observe that the symbol of an elliptic operator gives rise to a class in $K(T^*M)$. If the operator acts on smooth sections of a vector bundle $S$, then its symbol is a map $T^*M \to End(S)$ which is invertible away from the origin; Atiyah's "clutching" construction produces the relevant K-theory class. Second, one constructs an "analytic index" map $K(T^*M) \to \mathbb{Z}$ which sends the symbol class to the index of $D$. The crucial point about the construction of this map is that it is really just a jazzed up version of the basic case where $M = \mathbb{R}^2$, and in that case the analytic index map is the Bott periodicity isomorphism. Third, one constructs a "topological index map" $K(T^*M) \to \mathbb{Z}$ as follows. Choose an embedding $M \to \mathbb{R}^n$ (one must prove later that the choice of embedding doesn't matter) and let $E$ be the normal bundle of the manifold $T^*M$. $E$ is diffeomorphic to a tubular neighborhood $U$ of $T^*M$, so we have a composition
$K(T^* M) \to K(E) \to K(U) \to K(T^*\mathbb{R}^n)$
Here the first map is the Thom isomorphism, the second is induced by the tubular neighborhood diffeomorphism, and the third is induced by inclusion of an open set (i.e. extension of a vector bundle on an open set to a vector bundle on the whole manifold). But K-theory is a homotopy functor, so $K(T^* \mathbb{R}^n) \cong K(\text{point}) = \mathbb{Z}$, and we have obtained our topological index map from $K(T^*M)$ to $\mathbb{Z}$. The last step of the proof is to show that the analytic index map and the topological index map are equal, and here again the basic idea is to invoke Bott periodicity. Note that we expect Bott periodicity to be the relevant tool because it is crucial to the construction of both the analytic and topological index maps - in the topological index map it is hiding in the construction of the Thom isomorphism, which by definition is the product with the Bott element in K-theory.
To recover the cohomological formulation of the index theorem, just apply Chern characters to the composition of K-theory maps which defines the topological index. The K-theory formulation of the index theorem says that if you "plug in" the symbol class then you get out the index, and all squares with K-theory on top and cohomology on the bottom commute except for the "Thom isomorphism square", which introduces the Todd class. So the main challenge is to get an intuitive grasp of the K-theory formulation of the index theorem, and as I hope you can see the main idea is the Bott periodicity theorem.
I hope this helps!
As Johannes Ebert said, it's best if at first you stay away from boundary value problems. For some elliptic operators there may not even exist local boundary conditions satisfying the conditions guaranteeing Fredholmness; the Dolbeault operator is such an example. Therefore often one has to deal with pseudo-local boundary value problems such as the Atiyah-Patodi-Singer boundary condition.
A pseudo-diff operator on a closed manifold is Fredholm iff it is elliptic and the index is determined by the principla symbol, which is an element in the $K$-theory of a commutative algebra. For a boundary value problem Fredholmness is a much more subtle issue. It imposes restrictions on the type of boundary value conditions allowed (think Lopatinskii-Schapiro) and as Boutet de Monvel has shown almost four decades ago, the index is determined by the symbol of the problems which is an element in the $K$-theory of a certain non-commutative algebra; see e.g. this paper and the references therein.
The index of an operator on a closed manifold is eminently computable. In most geometric applications it can be reduced to the computation of the indices of a few classical operators: the spin and spin-c Dirac operators, the Hodge-de Rham operator (leading to the Gauss-Bonnet and the Hirzebruch signature operator), Dolbeault operator (leading to the Riemann-Roch-Hirzebruch formula).
The reduction to these cases requires good knowledge of representation theory, differential geometry and extensive familiarity with the theory of characteristic classes.
For manifolds with corners things are even more nebulous; same for most noncompact manifolds. In any case, to paraphrase one of my former professors, if you can describe a PDE problem explicitly, and you can prove its Fredholmness, then the index theorem will give you an answer as explicit as your question.
Best Answer
The Euler operator $d+d^*$ of a spin manifold is the spin Dirac operator twisted by the $\mathbb Z/2$-graded spinor bundle $W=S^+\ominus S^-$, as explained in Heat Kernels and Dirac Operators by Berline, Getzler, Vergne [BGV, chapter 4.1]. The Chern character $\mathrm{ch}(W)$ equals $e(TM)\hat A(TM)^{-1}$, see [BGV] or Nicolaescu's notes. The cohomological index theorem therefore gives $$\mathrm{ind}(d+d^*)^+=(\hat A(TM)\wedge\mathrm{ch}(W))[M]=e(TM)[M]$$
The de Rham representative of $e(TM)$ is given by the Pfaffian, and you get your second formula [BGV, Theorem 4.6].
The formulas above are pairings of "characteristic cohomology classes" with "fundamental homology classes". If you regard the Dirac operator as a fundamental $K$-homology class for the $K$-orientation of the tangent bundle given by the chosen spin structure, then the left hand side also constitutes a pairing of the $K$-theory class of the spinor bundle with the corresponding fundamental class.
To avoid the spin condition, you define the ``twist Chern character'' $\mathrm{tr}(\mathrm{exp}(-F^{W/S}))$ as explained in [BGV, chapter 4.1]. The formulas above still hold.
You can even get rid of orientability by regarding $e(TM)\in H^{\dim M}(M,o(TM))$ as a cohomology class twisted by the orientation bundle. Similarly, the Pfaffian is in fact a differential form twisted by the orientation bundle. Then all formulas above make sense without an orientation of $TM$.
On the other hand, the Euler number is the "trace" of id$_M$ in a sense explained nicely here (Def 2.2) - no matter if you count cells or dimensions of (co-) homology groups. To relate it to the pairings above, you may use either Hodge theory, or the Gauss-Bonnet-Chern theorem, or deduce $e(TM)[M]=\chi(M)$ from the Poincar'e-Hopf theorem, e.g. using Morse theory. It seems that because $\chi(M)$ and $e(TM)[M]$ are different kinds of objects, some work is needed for this step.