Yes or no, depending on the era
If your core question is whether or not Starfleet vessels are free to travel through Klingon space, then the answer depends heavily on the time period, as the nature of relations between the Federation and the Klingon Empire evolves greatly over time.
In Archer's time (during which Starfleet existed but the Federation did not, at least not yet), there were no formal relations between Earth and the Klingon Empire, yet no open hostilities either. In the first episode "Broken Bow", Archer's Enterprise was allowed to travel as far as the Klingon homeworld of Qo'noS in order to return a Klingon citizen to the Empire, but permission to enter Klingon space was brokered by the Vulcans through diplomatic channels.
It is doubtful that Archer could have entered Klingon territory without those diplomatic discussions. For instance, a Tellerite bounty hunter learned the hard way that Klingon space is not open to outsiders, as recounted in the Enterprise Season 2 episode "Bounty":
SKALAAR: My brother and I were hauling a shipment of fire-salt. I thought I could trim two or three days off our journey by cutting across the most insignificant corner of Klingon space. I learned very quickly there's no such thing as an insignificant corner of Klingon space. We were lucky to escape with our lives, though we did pay a price.
In Kirk's time (the 23rd Century), relations had degenerated into periods of both open and implicit warfare between the Federation and the Empire, including the establishment of a "Neutral Zone" between their territories which was not dismantled until the Khitomer Accord, whose negotiations began in Star Trek VI: The Undiscovered Country. Generally speaking, during Kirk's time as captain, no Starfleet ship could travel freely into Klingon space without facing armed conflict.
(Above: Colonel West, as depicted in The Undiscovered Country, presenting a plan to the Federation President for sneaking into the Klingon Empire to rescue Kirk and McCoy from the prison at Rura Penthe.)
In the TNG-era, we witness post-Khitomer relations between the Empire and the Federation. The Neutral Zone has been dismantled by this time (not to be confused with the Neutral Zone between the Romulan Star Empire and the Federation, which persisted) and there are diplomatic relations between the two powers (although this was disrupted for a short time during DS9).
During the peace, it seems that Starfleet vessels had some liberty to travel into the Empire. For instance, in TNG "Sins of the Father", Picard orders a sudden course change direct to Qo'noS:
PICARD: We're changing course. Set coordinates for the First City of the Klingon Imperial Empire.
(Let's not get started about "Imperial Empire"....)
Of course, they may have made their intentions known after the course change by contacting the Klingon High Command directly, although such dialogue does not occur on screen. If they had, then their request to travel was not denied. In any case, they were able to make their way to Qo'noS unimpeded.
Also, there is dialogue mentioning a Klingon ship in Federation space under routine circumstances. In "A Matter of Honour", while the Enterprise is docked at a Federation Starbase, we hear the following:
PICARD: It's been suggested that an officer from the Enterprise might participate in the [exchange] programme.
RIKER: That's probably a good idea.
PICARD: Well, there is a Klingon vessel in the area.
RIKER: I don't recall hearing of a Federation officer serving ever on a Klingon vessel.