Did the treaty pass with bipartisan support?
Yes. Protocol to the North Atlantic Treaty of 1949 on the Accession of Montenegro was ratified by the US Senate. The vote was 97 - 2 (roll call on senate.gov).
Rand Paul (R-KY) and Mike Lee (R-UT) voted "Nay". John Isakson (R-GA) abstained.
Did Rand Paul explain his reasoning for objecting to the treaty?
Yes, he published an op-ed on time.com: Sen. Rand Paul: Montenegro Joining NATO Is Against U.S. Interests. In general, Sen. Paul was against expanding financial and military commitments of the US to NATO:
Adding a country with fewer than 2,000 soldiers to NATO is not in our self-interest. There is no national security interest that an alliance with Montenegro will advance. If we invite Montenegro into NATO, it will be a one-way street with the U.S. committing to defend yet another country.
He also claimed that the Treaty is mainly a political gesture:
Advocates of allowing Montenegro to join NATO admit as much. The Senate hearing on admitting Montenegro to NATO was really just a Russia-bashing session. Not one word was said of how allowing Montenegro into NATO would advance our national security.
...
Those who want to allow Montenegro into NATO believe that unless the whole world joins NATO, Russia will conquer the world. The truth is, as always, more complicated.