Here are a couple ways to look at the problem.
First, we should probably be more explicit about what we mean by "combine." The result of a computer's computation is some _composition_ of its fundamental operations. If all those operations are linear, the composition must be linear (let h(x)=f(g(x)) be finite-dimensional linear functions, then f(x)=Ax and g(x)=Bx for some matrices A,B, and you can verify that h(x)=(AB)x -- i.e., h is linear -- then you can chain that result together for any finite number of compositions to show that any halting program is linear).
The links you gave require a different definition of combination from composition. Yes, nice enough functions can be _locally_ approximated by lines, but those lines aren't composed to give the final result; they're spliced together piecewise, and that splicing operation is nonlinear. If your computer's fundamental operations are all linear then that splicing operation can't be implemented, so the whole nonlinear combination can't be implemented either.
To the other evidence (deep learning, binary functions), the apparent contradiction arises because neither deep learning nor binary functions are inherently linear:
Deep learning does have large linear components (partly from a virtuous cycle of linear stuff being easy to compute and analyze, then hardware being designed to implement linear stuff more efficiently resulting in the status quo where there's a huge body of knowledge/software/hardware making large linear components the easy path to good results in a lot of cases), but critically they also have small nonlinear portions that enable them to approximate any nice enough function, not just the linear ones (if you want to look it up further, introductory search terms include "activation function", "rectified linear activation unit", and "sigmoid").
For the binary function example you can get away with a counting argument to show that OR isn't linear for any valid definitions of addition (i.e., they form groups) over 1-bit and 2-bit elements (even weird ones like assuming 2-bit elements add together like the klein 4-group):
- Pick a 3/1 unbalanced binary function like OR (which maps three 2-bit elements to 1 and one of them to 0).
- In the 4x4 table of all possible combinations of f(a+b) you'll have 12 1s and 4 0s.
- In the 4x4 table of all possible combinations of f(a)+f(b) you'll have 6 of either 1 or 0 and 10 of the other.
- 12,4 equals neither 6,10 nor 10,6, so the two tables aren't equal. We conclude that f(a+b)!=f(a)+f(b) for some 2-bit elements a,b.
- Hence, OR isn't linear (and neither are AND, Implies, ImpliedBy, and their negations by similar logic).