The new StringTemplate in V10 is a nice way to do this. Here a string is constructed for use as a plot label. The code could also be used directly as the option value in the plot function.
In[2]:= n = 10; m = 20;
In[3]:= label =
StringTemplate["solution with `1` x `2` grid points"][n, m]
Out[3]= "solution with 10 x 20 grid points"
In the first case, you are using StringTemplate incorrectly. StringTemplate[“string”] produces a TemplateObject which needs to be applied to arguments. Since all you want is the string as written, that is not useful here.
Note in my example above, the StringTemplate is applied to the argruments [n,m].