Yes, it converges uniformly. No, the M-test will not work - if you could find those $C_n$ that would show the series converges absolutely, which is not so. But:
Define $$s_n(x)=\sum_{j=1}^n\frac{\cos(j+x)}{j},$$ $$t_n=\sum_{j=1}^n\frac{\cos(j)}{j},$$ $$r_n=\sum_{j=1}^n\frac{\sin(j)}{j}.$$Then $$s_n(x)-s_m(x)=\cos(x)(t_n-t_m)-\sin(x)(r_n-r_m),$$so $$|s_n(x)-s_m(x)|\le|t_n-t_m|+|r_n-r_m|.$$Since $t_n-t_m\to0$ and $r_n-r_m\to0$ as $n,m\to\infty$ this shows that $s_n(x)-s_m(x)\to0$ uniformly; hence your series converges uniformly.
Details added, in reply to a comment: Let $\epsilon>0$. There exists $N$ so that $$|t_n-t_m|+|r_n-r_m|<\frac\epsilon2+\frac\epsilon2=\epsilon\quad(n,m>N).$$So the inequality above shows that $$|s_n(x)-s_m(x)|<\epsilon\quad(n,m>N),$$hence $$|s_n(x)-s(x)|=\lim_{m\to\infty}|s_n(x)-s_m(x)|\le\epsilon\quad(n>N),$$which says precisely that $s_n(x)\to s(x)$ uniformly.
You say the Weierstrass test doesn't talk about bounded intervals, and you are right. But, what it does talk about is uniform convergence on a given set $A$; if $\sum\limits_{n=1}^{\infty}\sup\limits_{x\in A}|f_n(x)|<\infty$, then the series converges uniformly on $A$ (and recall that uniform convergence on $A$ implies uniform convergence on every subset of $A$). In other words, take $M_n=\sup\limits_{x\in A}|f_n(x)|$.
Let's look at the series $\sum\limits_{n=1}^{\infty}\frac{x^{2n}}{(2n)!}$. Here, we have $f_n:\Bbb{R}\to\Bbb{R}$, $f_n(x)=\frac{x^{2n}}{(2n)!}$. Suppose $A$ is any bounded interval. This means there exists some $r>0$ such that $A\subset [-r,r]$. We have
\begin{align}
\sum_{n=1}^{\infty}\sup_{x\in A}\left|\frac{x^{2n}}{(2n)!}\right|\leq
\sum_{n=1}^{\infty}\sup_{x\in [-r,r]}\left|\frac{x^{2n}}{(2n)!}\right| \leq
\sum_{n=1}^{\infty}\frac{r^{2n}}{(2n)!}<\infty.
\end{align}
The first estimate should be obvious, since $A$ is contained in $[-r,r]$; this is just a basic property of supremums and set inclusions. The second inequality is actually an equality in this special case; I left it as a weak inequality just to emphasize that we don't have to be (and shouldn't aim to be unless explicitly instructed so) super precise with the estimates. All we want to do is show a certain numerical series is finite. The final step of claiming the series is finite can be done for example using the ratio test. In fact the final series equals $\cosh(r)-1$.
All the hypotheses of Weierstrass' M-test are satisfied, hence the series converges uniformly on $A$. Since $A$ was taken to be an arbitrary bounded subset of $\Bbb{R}$, this proves that the series converges uniformly on every bounded subset of $\Bbb{R}$.
In about 95% of situations, you can prove uniform convergence simply by the Weierstrass M-test (very rarely have I had to use some other method, such as Dirichlet's test; in fact I haven't used it recently, so much so that I kind of even lose track of the precise assumptions).
The Weierstrass M-test deals with uniform convergence of arbitrary functions. Specifically for power series, there is a very slight improvement. The essence is still Weierstrass' test. Anyway, the statement is:
Let $\{a_n\}_{n=0}^{\infty}$ be a sequence of complex numbers and $z_0$ a non-zero complex number such that the series $\sum_{n=0}a_nz_0^n$ converges. Then, for any $0\leq r<|z_0|$ (note the strict inequality), the series $\sum_{n=0}^{\infty}a_nz^n$ converges absolutely and uniformly on the closed disk $D_r=\{z\in\Bbb{C}\,:\, |z|\leq r\}$.
We assume $z_0\neq 0$ because the series always converges at the origin; so we're just excluding the trivial case. The "strength" of this theorem is that our hypothesis only tells us the series $\sum_{n=0}^{\infty}a_nz_0^n$ converges; we don't know anything about absolute convergence.
TO prove this, note that since the series converges, the general summand must tend to zero: $a_nz_0^n\to 0$ as $n\to\infty$. In particular, it is a bounded sequence; i.e $M:=\sup\limits_{n\geq 1}|a_nz_0^n|<\infty$. Now, for any $0\leq r<|z_0|$, we have
\begin{align}
\sum_{n=0}^{\infty}\sup_{|z|\leq r}\left|a_nz^n\right|=\sum_{n=0}^{\infty}\sup_{|z|\leq r}\left|\frac{z^n}{z_0^n}a_nz_0^n\right|\leq\sum_{n=0}^{\infty}\frac{r^n}{|z_0|^n}M<\infty,
\end{align}
by the ratio test with the common ratio $\rho=\frac{r}{|z_0|}<1$ (actually, you can explicitly sum the geometric series; the answer is $\frac{M}{1-(r/|z_0|)}<\infty$). By Weierstrass' test, it follows the series converges uniformly on the closed disk $D_r=\{z\in\Bbb{C}\,:\, |z|\leq r\}$, hence the proof is complete.
Best Answer
Hint: If $\sum f_n$ converges uniformly on a set $E,$ then $\sup_E|f_n|\to 0.$