You should use the name that was used at the time. So probably
Santa Fé de Nuevo México, New Spain 1598
"Spanish explorers recorded this region as New Mexico (Nuevo México in Spanish) in 1563. In 1581, the Chamuscado and Rodríguez Expedition named the region north of the Rio Grande "San Felipe del Nuevo México".[13] . . . Before statehood, the name "New Mexico" was applied to various configurations of the U.S. Territory, to a Mexican state, and to a province of New Spain, all in the same general area, but of varying extensions.[16]"
It appears that the English New Mexico Territory, United States (1848-1912) and New Mexico, United States (1912- ) were not used until the mid 1800s. Before that it was the Spanish Nuevo México, New Spain (1598-1821), Nuevo México, Mexico (1821-1848).
That said, I think your "Nuevo México, Nueva España" and "Nuevo México, México." would be more accurate.