The use of typography to censor words was to avoid breaking obscenity laws, and it was blasphemous to make fun of religion. Religious words were censored more than "normal" swear words, and were only censored when used as part of oaths; normal use was unbleeped. Dashes were used to obfuscate from the mid-17th century and throughout the 18th century and asterisks were common from the 19th century on.
Edit: I've confirmed these in the EEBO database.
The earliest that has a full PDF is in Sodom or the Quintessence of Debauchery (1684) by the Earl of Rochester, which is chock full of all sorts of uncensored sexual language but bleeps out "heaven[s]", "almighty", "God[s]" (although there's a single "p—s"), for example:
The earliest I found is John Philips' Sportive Wit (1656) and contains manyis chock-full of bleepos. Here's one poemsome extracts.
Here 's a Health to my Lady Kent,
that hath a bounsing C —--;
And to my Lord her husband.
that tickl'd my Lady Hunt.
These are they bear the sway
And keep the money;
Which he may better do,
Than his wife's ---
She hath a buttock plump,
Keep but thy T--- whole:
She will hold up the rump
With her black A --- hole.
About this T--- there stuck
Many a broken plum,
All fritter'd with a fart
Which came out of her bum,
And made it smart.
Take a Lady in the grasse,
Clap her ---
--- her well and let her passe;
Upon the bed then let her tumble,
Put it in,
Put it in she'l never grumble.
And you shall never gain a penny,
But still they will be plucking.
And think that they shall never have
Their bellies full of ---.
Come husband, away with this filthy curre,
It makes my flesh to rise,
He left off all, and to her did fall,
And slipt between her ---
WHen I do smoak my nose with a pipe of Tobacco after a feast,
Then down let I my hose, and with paper do wipe mine — like a beast.
It so doth please my minde,
It doth so ¿asecase behinde,
For to wipe,
For to wipe my ¿eweltewel.
Tobacco's my delight,
So 't is mine to sh —
Oh fine smack,
Oh brave ¿ackcack my jewel.
Searching Early English Books Online, I've found an earlier typo-bleepo.
1651
James Smith's The Loves of Hero and Leander a mock poem : with marginall notes, and other choice pieces of drollery (page 14, EEBO):
He tooke him to a trusty rock,
And stript him to the ebon nock.
And being naked look't like Mars,
With purple scab upon his A---