A good way to add more PvE content to Klingon (and future hostile factions) players is to have counter missions with Federation players, in certain zones.
For Federation players ordered to patrol Regulus. But a Klingon player is ordered to scout Regulus. Eventually the two would meet and do 1 on 1 battle.
Or regular PvE:
Klingons being the early antagonists of many of the early Federation missions, why not have the Klingon player do the missions that lead up to that Federation mission? Like on the Paris Mission, you are ordered down to subjugate the Federation Ambassador, instead of rescuing him.
I'm sure Klingons would love to partake the Tribble mission and go Tribble hunting!