Normally on Rosh Chodesh, people in most shuls I've seen take off their tefillin after kaddish, but don't wrap them. This is also what Artscroll nusach Ashkenaz says.
What about if you daven alone and there's no kaddish? If you follow this minhag, should you wrap your tefillin? We seem not to be too concerned about hefsek between ashrei(+uva letziyon) and shemoneh esrei, since at shacharit we put kriyat shema between pesukei dezimra, which is the extension of ashrei, and shemoneh esrei, and at mincha on Shabbos and fast days we put leining in between.
On the other hand, we do announce things (משיב הרוח, יעלה ויבא, ...) between kaddish and shemoneh esrei instead of before kaddish, so maybe there's something more subtle happening with regard to wrapping tefillin that I'm not appreciating.