Your recurrence relation falls into Case 1: $f(n) = n \log n$ is $O(n^{log_{b}{a}-\epsilon}) = O(n^{2-\epsilon})$.
To show why this is Case 1, as Louis says, logarithmic functions ($\log n$) are asymptotically bounded by polynomial functions ($n^a$, where $a > 0$). This can be shown by taking the limit:
$$
\lim_{n \to \infty} \frac{\log n}{n^a} = 0
$$
through L'Hôpital's rule. In particular, $\log n \in O(n^{1-\epsilon})$ for small $\epsilon$. (We can go even further and say that $\log n \in o(n^{1-\epsilon})$.)
Then by multiplying both sides by $n$, (an allowed operation in big-O notation), $n \log n \in O(n^{2-\epsilon})$.
Therefore by the Master Theorem, $T(n)$ is $\Theta(n^2)$.
Starting where you left off:
$S(m)=S(m/2)+ \Theta(\lg m)$
Compared this to the generic recurrence:
$T(n) = aT(n/b) + f(n)$
Let's address the questions, you raised.
What does "polynomially" larger mean?
A function $f(n)$ is polynomially larger than another function $g(n)$, if $f(n) = n^i g(n)/t(n)$, where $t(n)$ is some sub-polynomial factor such as $\log n$, etc that appears in $g(n)$. In other words, we want to see, ignoring sub-polynomial and constant factors, if $f(n)$ is a polynomial multiple of $g(n)$.
Does case 2 apply here?
Recall that Case 2 of the master theorem applies when $f(n)$ is roughly proportional to $n^{\log_b a}\log^kn$ for some $k \ge 0$. Now, applying all this to your equation above, $a = 1$, $b=2$ and $f(m) = \Theta(\log m)$. This give $k = 1$ and since $m^{\log_2 2^0}\log^km = \Theta(\log m)$, case 2 does apply.
What is the solution using Case 2?
Generally, when case 2 does apply, the solution is always of the form $\Theta(n^{\log_b a}\log^{k+1}n)$. So, in your case, it'll be $\Theta(\log^2 m)$ as you've already figured.
Best Answer
Step 4 could use some more work. Namely, you need to show that $(\log(n))^{2} \in O(n^{c})$ for some $c < 1/2$. This shouldn't be too hard. For example, take $c = 1/3$. We have that: \begin{align*} \lim_{n \to \infty} \frac{(\log(n))^{2}}{n^{1/3}} = 0. \end{align*}
I'll leave it to you to fill in the details for the limit computation.
So $(\log(n))^{2} \in O(n^{1/3})$ (actually, $(\log(n))^{2} \in o(n^{1/3}))$.
Your reasoning is otherwise fine.