Why adding combinations of features would increase performance of linear SVM? I have a dataset of ~5000 elements represented by vectors composed by ~30 binary values (0 or 1) 
on which I am performing binary classification with SVM with linear kernel (I use the Scikit learn lib).

For curiosity, I tried to add an extra feature that consists in a AND between two others (remember that all my features are boolean). The result was that the performance of the SVM improved. I was surprised by this improvement because the AND operation is equivalent to a multiplication, therefore I would expect that my SVM, as every linear classifier, was somehow naturally already taking into account mutiplications between features.

What is wrong with my theoretic understanding of SVM ?
Multiplication is not a linear operation. Your linear SVM constructs a (hyper-)plane
$$
w_0 = w_1 x_1 + w_2 x_2
$$
for some weights $w_0, w_1, w_2.$

By introducing the AND-feature, you add another dimension:
$$
w_0 = w_1 x_1 + w_2 x_2 + w_3 x_1 x_2.
$$

It might well be that your two-dimensional data set is not linearly separable, but the three-dimensional data set is. 

A small addition: Would adding the OR-feature increase performance even further? No, because it is a linear combination of the other three features: $x \vee y = x + y - (x \wedge y)$ where $\vee$ is OR and $\wedge$ is AND.