The starting point is: What is the most general form of a "linear quaternion polynomial"?
By linear here, I do not mean a linear map, but general polynomials limited to at most first degree in the variable. This is complicated by quaternion multiplication not commuting, so there may also be a more appropriate term for these "polynomials", but hopefully it is clear from context below what I mean.
As a first stab, I guessed that every such polynomial could be put in the form: $$ f(q) = aqb + cq + qd + e $$ with quaternion constants $a,b,c,d,e$.
But I'm really struggling to prove that adding two functions of this form results in another function of this form. So maybe that is not the most general form?
More explicitly, let $$ \begin{aligned} f(q) &= f_0qf_1 + f_2q + qf_3 + f_4 \\ g(q) &= g_0qg_1 + g_2q + qg_3 + g_4 \\ h(q) &= f(q) + g(q) = h_0qh_1 + h_2q + qh_3 + h_4 \\ \end{aligned} $$
How can I solve for the constants in $h(q)$ given the constants in $f(q),g(q)$?
Or if this is provably impossible, what is the most general form of a linear quaternion polynomial?
EDIT:
Hand wavy, but maybe I should expect that the most general form would allow $$ \begin{aligned} (q_0, q_1, q_2, q_3) \rightarrow &( \\ &a_{00} q_0 + a_{01} q_1 + a_{02} q_2 + a_{03} q_3 + a_{04}, \\ &a_{10} q_0 + a_{11} q_1 + a_{12} q_2 + a_{13} q_3 + a_{14}, \\ &a_{20} q_0 + a_{21} q_1 + a_{22} q_2 + a_{23} q_3 + a_{24}, \\ &a_{30} q_0 + a_{31} q_1 + a_{32} q_2 + a_{33} q_3 + a_{34} \\ &) \\ \end{aligned} $$ Which suggests that what I wrote is not even close to the most general form for a quaternion linear polynomial.
If we label the quaternion basis as $h_0 = 1, h_1 =i, h_2 = j, h_3 = k$, then maybe the general form is: $$ f(q) = a_0 + \sum_{i,j} c_{ij}\ h_i\ q\ h_j $$ where $c_{i,j}$ are real value constants and $a_0$ is a quaternion constant.
That seems excessive. Is it really not possible to reduce this further?
In this form it is at least easy to add two linear polynomials, so could be a good stepping stone if there is a more reduced version.
Let $Q$ be a quaternion algebra (I assume that you want to work with $Q=\mathbb{H}$, the usual Hamilton quaternions, but this works for general quaternion algebras). Then we have a linear map (sometimes called the "sandwich map") $$ Q\otimes Q\to L(Q)$$ where I use $L(Q)$ for the linear maps $Q\to Q$, given by $$a\otimes b\mapsto (q\mapsto aqb).$$
So the image of $a\otimes b$ is one of your "linear polynomials". You also use the image of $1\otimes d$ and $c\otimes 1$ when you have "one-sided" products. In the end the linear part of your initial guess is exactly the image of the tensors of the form $a\otimes b+c\otimes 1+1\otimes d$.
Now the result is the following: this map $Q\otimes Q\to L(Q)$ is an isomorphism (of vector spaces).
First, this means that your "linear polynomials" are in fact all affine maps $Q\to Q$ (since you allow arbitrary sums), since all elements of $Q\otimes Q$ are sums of pure tensors $a\otimes b$.
But since not all tensors can be written as $a\otimes b+c\otimes 1+1\otimes d$, your initial guess is not enough, as you suspected. So actually your question can be reduced to: how many pure tensors are necessary to write a general element of $Q\otimes Q$? I'll let you think about that.