Let me explain here an actually useful characterisation of a "tensor" that is not as oldfashioned as the one of how a "tensor" transforms under change of coordinates. In the process I hope I can clarify why the difference between two connexions is a "tensor".
I shall assume smoothness everywhere.
A connexion, the way it is defined by the Original Poster, $D:\Gamma(E)\to\Gamma(E\otimes T^*M)$ takes smooth sections of the vector bundle $E$ to differential $1$-forms taking values at sections of $E$. One can see this by recognising that $\Gamma(E\otimes T^*M)\cong\Gamma(E)\otimes_{C^\infty(M;\mathbb{R})}\Gamma(T^*M)\cong\mathrm{Hom}_{C^\infty(M;\mathbb{R})}(\mathfrak{X}(M;\mathbb{R});\Gamma(E))$, where I am identifying the $C^\infty(M;\mathbb{R})$-module of sections of the tangent bundle $\Gamma(TM)$ with vector fields of $M$, as derivations on the algebra $C^\infty(M;\mathbb{R})$ ---I do recommend Lee's Introduction to smooth manifolds, or Wald's General Relativity if one is not used to these notions.
That being said, let $s\in\Gamma(E)$ a section of $E$, $X\in\mathfrak{X}(M;\mathbb{R})$ a vector field on $M$ and $f\in C^\infty(M;\mathbb{R})$ a smooth function. By applying the definition of a connexion (as given by the Original Poster), one can readily see that
$$Ds(fX)=fDs(X)$$
and
$$Dfs(X)=X(f)s+fDs(X) \ .$$
Remark: this last property is usually a defining property for a connexion on a vector bundle when it is defined globally, as opposed to the Original Poster's local definition.
Now, if $D$ and $D'$ are two connexions defined on $E$, their difference satisfies
$$(D-D')s(fX)=f(D-D')s(X)$$
and
$$(D-D')fs(X)=f(D-D')s(X) \ .$$ This last equality ---which does not hold for any of the connexions alone--- that characterise their difference as being a "tensor"; their difference is actually a differential $1$-form taking values on the sections of $E$.
The reason why the difference of two connexions satisfies $(D-D')s(fX)=f(D-D')s(X)$ is because each contribute with an extra term $X(f)s$, $Dfs(X)=X(f)s+fDs(X)$ is a sort of Leibniz rule.
A "tensor" is just a mapping that when its arguments are multiplied by functions, it behaves as a linear mapping regarding this $C^\infty(M;\mathbb{R})$-module structure. This is not as precise as I like, but let me show an example with the metric "tensor" (a riemanninan structure $\mathrm{g}$): with vector fields $X,Y,Z\in\mathfrak{X}(M;\mathbb{R})$ and smooth function $f\in C^\infty(M;\mathbb{R})$, the riemannian metric satisfies $\mathrm{g}(X+fY,Z)=\mathrm{g}(X,Z)+f\mathrm{g}(Y,Z)$.
This type of behaviour, with respect to multiplication by functions, guarantees that these "tensors" only depend on what happens at a point. And the way they transform under diffeomorphisms (change of coordinates) can be deduced from that property.
Homework for the Original Poster: since you know how covariant and contravariant tensors transform under change of coordinates, and I claimed that the difference between two connexions is pretty much a $1$-form taking values on sections of $E$: use a local basis for sections of $E$, and another one for the vector fields of $M$, and show how the values of $Ds(X)$ and $(D-D')s(X)$ change under a change of coordinates. Hint: exploit how the connexions behave when multiplying their arguments by functions.
Let $\nabla_0\colon C^\infty(M,L)\to \Omega^1(M,L)$ be a reference connection. Then any other connection on $L$ can be written as $\nabla_A = \nabla_0+A$, where $A\in \Omega^1(M,\mathbb C)\cong \Omega^1(M,\mathrm{End}(L))$. This is what makes $\mathcal{A}(L)$ into an affine space.
Let now $(U_\alpha)$ be an open cover of $M$ and $s_\alpha\in C^\infty(U_\alpha,L|_{U_\alpha})$ be collection of non-vanishing sections. These automatically trivialise the bundle and thus there exist transition functions $z_{\alpha\beta}\in C^\infty(U_{\alpha\beta},\mathbb C)$ on $U_{\alpha\beta} =U_\alpha\cap U_\beta$ such that
$$s_\alpha = z_{\alpha\beta}s_\beta \quad \text{ on } U_{\alpha\beta}. \tag{1}$$
Moreover, we can express $\nabla_A s_\alpha$ via some $\omega_{\alpha}\in \Omega^1(U_\alpha,\mathbb C)$ as follows:
$$
\nabla_A s_\alpha = \omega_{\alpha} s_\alpha \tag{2}
$$
Now apply $\nabla_A$ to $(1)$ and use the Leibniz rule:
$$
\omega_\alpha s_\alpha = \nabla_A(s_\alpha) = dz_{\alpha\beta} s_\beta + z_{\alpha\beta} \nabla_As_{\beta} = dz_{\alpha\beta} s_\beta + z_{\alpha\beta} \omega_\beta s_\beta = \frac{dz_{\alpha\beta}}{z_{\alpha\beta}} s_\alpha + \omega_\beta s_\alpha
$$
Since the $s_\alpha'$s don't vanish we get the following relation you encountered:
$$
\omega_\alpha = \frac{dz_{\alpha\beta}}{z_{\alpha\beta}} + \omega_\beta \tag{3}
$$
What I've explained is how to associate to a connection $\nabla_A$ a collection of $1$-forms $(\omega_\alpha)$ satisfying relation $(3)$. Now try to reverse engineer a connection $\nabla_A$ out of the $1$-forms!
Best Answer
The induced connections become natural to understand by considering the parallel transport maps.
The operation of taking the dual or the tensor product of vector spaces are functors, so for the parallel transport maps there are natural induced maps on the dual spaces and tensor products:
For a smooth curve $\gamma:I\to M$ and $t_0,t_1\in I$ let
$$ P^\nabla:E_{\gamma(t_0)}\to E_{\gamma(t_1)} $$
be the parallel transport along $\gamma$ corresponding to $\nabla$. Then the parallel transport maps corresponding to $\nabla^\otimes$ and $\nabla^*$ are given by
$$ {(P^\nabla})^*:{E^*}_{\gamma(t_1)}\to {E^*}_{\gamma(t_0)},\;\;{(P^\nabla})^*(\varphi)(v)=\varphi({P^\nabla}(v))$$
$$P^\nabla\otimes P^\nabla:E_{\gamma(t_0)}\otimes E_{\gamma(t_0)}\to E_{\gamma(t_1)}\otimes E_{\gamma(t_1)},\;\;P^\nabla\otimes P^\nabla(u\otimes v)= P^\nabla(u)\otimes P^\nabla(v) $$ Since the connections can be recovered from the parallel transport maps $\nabla^*$ and $\nabla^\otimes$ are the unique connections with these properties.