What is an example of a (compact) manifold, which has two nonequivalent differential structures such that the Khomology groups are nonisomorphic? If no such example exists, i.e. "Khomology does not see the differential structure", then can someone give a heuristic explanation of why an object (originally at least) defined in terms of pseudodifferential operators does not depend on a choice of differential structure.

2$\begingroup$ Well, de Rham cohomology is also defined in terms of smooth stuff and doesn't end up depending on it. $\endgroup$ – Qiaochu Yuan Oct 6 '15 at 3:44
Khomology is usually not defined in terms of pseudodifferential operators. In fact, I don't even know which definition you mean.
Khomology is either defined as the dual of Ktheory (i.e., it is defined as the generalized homology theory associated to the Ktheory spectrum), which means that it only depends on the weak homotopy type of the space.
Or it is defined using Fredholm modules over the C*algebra $C_0(X)$ of continuous functions vanishing at infinity, which means that a priori it depends only on the homeomorphism type of the space.
Or it is defined using a geometric picture (cycles are compact spin$^c$manifolds with a Hermitian vector bundle and a continuous map to the space).
All three definitions can be applied to topological spaces, i.e., do not need a smooth structure on the space or the space being a manifold at all. All three definitions coincide for finite complexes.
This is more or less an addendum to AlexE's answer:
Even though the $K$homology groups themselves do not depend on the smooth structure there are classes in $K$theory, which can tell apart some of the smooth structures:
Let $\mathcal{S}(M)$ denote the group of isotopy classes of smooth structures on $M$ and $M_{\alpha}$ denote $M$ equipped with the smooth structure $\alpha$. The identity map induces a map on the corresponding sphere bundles $\varphi \colon SM_{\alpha} \to SM$. There is a unit $u \in K^0(SM)$, such that $\varphi_*([SM_{\alpha}]) = u \cap [SM]$, where $[SM] \in K_1(SM)$ denotes the fundamental class of the spin$^c$manifold $SM$ in $K$homology. The class $u$ descends to a unit $\theta(\alpha) \in K^0(M)$, such that $\pi^*(\theta(\alpha)) = u$, where $\pi \colon SM \to M$ is the bundle projection. It was proven by Jerome Kaminker that $\theta \colon \mathcal{S}(M) \to K^0(M)$ is a homomorphism and that there are smooth manifolds $M$ for which $\theta$ is nontrivial (see "Pseudodifferential Operators and differential structures").
This implies for example that the algebra of order $0$ pseudodifferential operators $\mathcal{P}_M$ depends on the smooth structure. To see this, note that it fits into an exact sequence $$ 0 \to \mathcal{K} \to \mathcal{P}_M \to C(SM) \to 0 $$ (where $\mathcal{K}$ are the compact operators) giving an element in $K_1(SM)$ by BDFtheory. This class agrees with the fundamental class $[SM] \in K_1(SM)$.