As for convincing Leto to allow the marriage of Paulette to Feyd, Jessica could have imprinted him if all else failed. But since we assume that Paulette would be a BG then we might as well just assume that Paulette herself would have insisted on the marriage and would have convinced Leto she wanted it and that it was for the good of the House. If Jessica and Paulette (and maybe even Thufir) were for it then Leto might relent. Gurney and Duncan would hate the idea but they would be overruled if it meant Atreides blood on the throne and actual peace between the two Houses. Plus there is also the possibility of tempting Leto with a CHOAM directorship, or subtly pressuring him into it in other ways. I don't think getting Leto to agree was going to be the major obstacle in the BG's entire breeding program.
The BG cared about sealing the breach because they needed the bloodlines, and it helped that the KH would have had royal blood as well when taking the throne. I doubt the BG cared at all about the Hark-Atr feud, other than that the assassination attempts that occur in kanly would be putting their genetic stock at risk.
As for Shaddam, he had no say in any of this other than to rubber stamp the plan.
Dune wrote:When my father, the Padishah Emperor, heard of Duke Leto's death and the manner
of it, he went into such a rage as we had never before seen. He blamed my mother
and the compact forced on him to place a Bene Gesserit on the throne. He blamed
the Guild and the evil old Baron. He blamed everyone in sight, not excepting
even me, for he said I was a witch like all the others. And when I sought to
comfort him, saying it was done according to an older law of self-preservation
to which even the most ancient rulers gave allegiance, he sneered at me and
asked if I thought him a weakling. I saw then that he had been aroused to this
passion not by concern over the dead Duke but by what that death implied for all
royalty. As I look back on it, I think there may have been some prescience in my
father, too, for it is certain that his line and Muad'Dib's shared common
-"In My Father's House," by the Princess Irulan
Once Paul was born Shaddam probably believed he still had a chance to retain control of the Empire. In order to remain Emperor he had to consent to the Grand Plan to take down House Atreides, however. The BG would then have to cut their losses and harvest Feyd's genetic material through Margot Fenring and delay the coming of the KH for a while.