Aside from checking them one at a time, is there any shortcut to finding a trinomial in $GF(2)[x]$ that is a multiple of a given polynomial $p(x)$, where $p(1) = 1$ and $p(x)$ has constant term 1?
I know I can assume that the constant term is 1 (otherwise the trinomial would be a multiple of some $x^k$ and I could divide that out); are there any other shortcuts?
What if I want the smallest trinomial that is a multiple of $p(x)$?
I believe there is no guarantee that a trinomial multiple of a given polynomial obeying the conditions you provided exists. A given trinomial of high degree will factor into a product of irreducible polynomials, whether one of them is your polynomial is random in nature.
In cryptology, randomized algorithms are used to find trinomial multiples of primitive polynomials and products of primitive polynomials. In that case, a statistical analysis tells one what degree this trinomial multiple is likely to be.
Since a primitive polynomial $f(x)$ over $\mathbb{F}_2$ of degree $d$ can be used as the generator polynomial of a Hamming code of length $2^d-1,$ and such a code is known to have minimum weight 3, it is guaranteed that $f(x)$ has a trinomial multiple of degree at most $2^d-1.$
Here is a link to a paper that talks about this subject.