Problem understanding the Expectation Operator I know that the Expectation Operator $E\{x\}$ four discrete values is
$$ \sum_k \alpha Pr(x = \alpha_k)$$

and its very intuitive when speaking out a formula which contains the Expectation Operator. But I often have some troubles when trying to apply it on real examples with numbers. 

E.g. the autocorrelation is completely obvious when given as sum like:
$$ r_x(\tau)=\sum_n x_n x_{n-\tau}.$$ However, often principles like autocorrelation, correlation, cross-correlation etc. are formulated with the $E$ Operator. For the autocorrelation:
$$ r_x(k,l) = E\{x(k)x^*(l)\}.$$
I assume this can be written as:
$$ r_x(\tau) = E\{x(k)x^*(k-\tau)\}.$$

The product is the same as in the sum above. However, the $E$ Operator implies that I need to know some probabilities. How can one quickly see that this is the same as above with $\alpha$ is somehow $x_n x_{n-\tau}$ and $Pr=1$? This can't always be the case. Otherwise one could always write the sum instead of the E Operator, couldn't he?

I think about the E Operator as if it is needed for different random processes. This would imply that I can't formulate e.g. a cross-correlation as a sum over all products between two signals, as I used to do. A formula like $r_{xy}(k,l)=E\{x(k)y^*(l)\}$ would then be a more general case and could not be applied on a simple numerical example, without making assumptions about the processes statistical properties.
Consider a discrete-time, discrete valued random process $X[n,s)$ whose samples $x[n]$ at integer index $n$ belong to range space $R_{X_n} = \{x_1,x_2,...,x_n\}$ of discrete valued random variables $X_n$ indexed by $n$, such that at each $n$, the value $x[n]$ is the result of the mapping by $X_n$ into $R_{X_n}$; i.e., $X[n,s) = X_n(s) = x[n]$, where $s$ is the sample output of the experiment performed at time $n$.

The expectetation of a particular random variable $X_n$ of the random process is
$$\mathcal{E} \{ X_n \} = \sum_{x_k \in R_{X_n}} x_k P_{X_n}(x_k) = \int_{-\infty}^{\infty} x f_{X_n}(x) dx $$
where those $x_k$ belong to the range space of the random variable $X_n$ and $P_{X_n}(x_k)$ are the probabilities of those values. Note that the integral definition is also available for those who would still like to use a continuous random variable approach with impulsive PDFs; $$f_{X_n}(x) = \sum_k P_{X_n}(x_k) \delta(x-x_k) $$

The correlation between two (real) random variables $X_n$ and $X_m$ is defined as
$$\mathcal{E} \{ X_n X_m \} = \sum_{k} \sum_{l} x_k x_l P_{X_n,X_m}(x_k,x_l) $$
where $P_{X_n,X_m}(x_k,x_l)$ is the joint probability mass function of the two random variables, and signifies the probability of the pair $(x_k,x_l)$ in the range space of the joint mapping.

When those two random variables belong to the same random process, then the correlation is defined as auto-correlation of the random process.

Note that the second sum in your post does not represent an expectation but rather a possibly ergodic estimate of it for a WSS random process.