Some licenses for Office 2007 allow installation on more than 1 device. Then there is no need to buy a new version. And if you uninstall it from the old machine and it's a retail version, you can use the same license on your new machine.

Anyway, https://products.office.com/en-us/buy/compare-microsoft-office-products shows that Office 2016 Professional comes with Publisher and is a one time purchase.
Office 2013 Professional has Publisher also; you can buy it for example via http://www.amazon.com/s/ref=nb_sb_ss_i_1_12?url=search-alias%3Daps&field-keywords=office+2013+professional&sprefix=office+2013+%2Caps%2C290

https://products.office.com/en-us/buy/office shows that Publisher 2016 is available as a separate product. You can add that to a Office 2016 Home and Student edition; the combination is cheaper.

Microsoft is chystal clear, I'd say. So it's somewhat strange you couldn't find it.
If you prefer to buy in a physical shop in stead of via the web, be sure to find a shop that is just as crystal clear.

Kees