I'll start out by saying I don't know the answer to Hal's question, but the following information may help to narrow it down.
The Montana Department of Transportation (MDT) maintains historical data on this route (and many others), but the data is very sparse prior to 1934. Main Street was likely improved/paved over the years on a number of different road segments at different times. MDT data reveals that there was "city construction" in 1918 and 1932, but the data does not include the locations of the segments that were improved or what type of improvement was done.
Main St. was added to the Federal Aid Primary Highway system in October of 1922, which made it eligible for federal and state funding.
The first MDT record of surface type appears as a paved surface in 1943, but I suspect it was paved long before that.
My guess is the record of when Main Street was first paved lies with the City of Miles City.