Heinrich Kiepert, Paphlagonia, Public Domain, via Wikimedia Commons
Paphlagonia was in northern Anatolia and was bordered by Bythnia to the west, Pontus to the east, and Galatia to the south.
"In the Homeric catalogue we find Pylæmenes leading the Paphlagonians as allies of the Trojans; from this Pylæmenes the later princes of Paphlagonia claimed their descent, and the country was sometimes from them called Pylæmenia." -Pliny, Natural History, 6.2.2
King Pylaemenes of the Trojan war dies at the hands of Menelaus in the Iliad 5.576. He is also famous for coming back to life in the Iliad 13.643-559 after his son is killed:
"Him (son of Pylaemenes) the great-hearted Paphlagonians tended, and setting him in a chariot they bare him to sacred Ilios, sorrowing the while, and with them went his father, shedding tears; but there was no blood-price gotten for his dead son."
About a thousand years later, the Kings of Paphlagonia were named Pylaimenes. and during the reign of Pylaimenes II, Mithridates VI Eupator made a deal with Nicomedes III of Bithynia to invade and split up Paphlagonia in 108/107 BC. There was a pretense as well that Pylaimenes had bequeathed his Kingdom to Mithridates V.
"The last king of Paphlagonia was Deïotarus, son of Castor, and surnamed Philadelphus, who possessed Gangra, containing the palace of Morzeus, a small town, and a fortress." -Strabo, Geography, a son of Nicomedes who was installed after Paphlagonia was taken by Bithynia. It seems the shared epithet ("Eurgetes" or "Benefactor") suggests the son or Nicomedes III who was also "Eurgetes" .
Between 107 and 101 BC, Nicomedes then invaded Cappadocia only to be subsequently conquered by Mithridates VI, who expanded his position as the dominant force in Asia minor and rival to Rome.
Entering then into an alliance with Nicomedes, [Mithridates VI of Pontus] invaded Paphlagonia, and divided it, after it was conquered, among his allies. But when information reached the senate that it was in possession of the two kings, they sent ambassadors to both, desiring that "the country should be restored to its former condition." Mithridates, thinking himself now a match for the power of the Romans, haughtily replied, that "the kingdom had belonged to his father by inheritance, and that he wondered that a dispute, which had never been raised against his father, should be raised against himself;" and, not at all alarmed by threats, he seized also on Galatia. As for Nicomedes, he replied that "as he could not maintain that he had any right to the country, he would restore it to its legitimate sovereign;" and, altering his son's name to Pylaemenes, the common name of the Paphlagonian kings, he assigned it to him; and thus, as if he had restored the throne to the royal line, he continued to occupy the country on this frivolous pretext."
-Justin, Epitome 37.4 For more on Mithridates use of his family members (and disposal of his family members) to control Cappadocia, see my note on "A Father's Support". A few years later when Tigranes, king of Armenia, with support from Mithridates VI, chased the Roman installed king Ariobarzanes out of Cappadocia, Sulla was sent to restore him to power circa 94 BC.
This coin either minted under Paphlagonian rule or after the invasion of Paphlagonia by Pontus and Bithynia. They are potentially minted in Gangra which Strabo reports as the residence of the last king of Pamphylia.
"The last king of Paphlagonia was Deïotarus,104 son of Castor, and surnamed Philadelphus, who possessed Gangra, containing the palace of Morzeus, a small town, and a fortress."
-Strabo, Geography, 12.3.41 
Kings of Paphlagonia, Pylaimenes II/III Euergetes (Circa 133-103 BC), AE20 4.98g Obv: Bust of Pylaimenes right, as Herakles, with club over shoulder and lion skin around neck Rev: ΒΑΣΙΛΕΩΣ / ΠΥΛΑΙΜΕΝΟΥ ΕΥΕΡΓΕΤΟΥ, Nike standing left, holding wreath and palm frond Ref: SNG BM 1552; SNG von Aulock 149
There is no shortage of portraits of Nicomedes II of Bithynia? On the basis of portrait, can we rule out his son as the person illustrated on this coin?
These next coins often attributed to the same period? surely there is some better evidence in finds of when these coins were struck?
Kings of Paphlagonia, Pylaimenes II/III Euergetes (Circa 133-103 BC), AE 3.85g, 17.4mm
Obv: Facing head of a bull
Rev: ΒΑΣΙΛΕΩΣ - ΠYΛΑΙΜΕΝΟΥ / ΕΥΕΡΓΕΤΟΥ, winged kerykeion
Ref: SNG BM 1555
Reference:
Glew, D. (1987). The Cappadocian expedition of Nicomedes III Eurgeter, King of Bythnia. Museum Notes (American Numismatic Society), 32, 23-55.
Pliny, Natural History
Smith, William Ed. (1854), Dictionary of Greek and Roman geography, Paphlagonia.
Braund, David. “Royal Wills and Rome.” Papers of the British School at Rome 51 (1983): 16–57.