Following up on some stories I heard of yaoi fans I know from conventions, and a lot of trips on the WayBack machine to find old/deleted posts following the first ban, I came down to this pretty consistent story both online and among the fans.
The original yaoi paddle was made as a prank between 2 friends. The one receiving it was a yaoi manga/doujishin artist, which made quite a bit of his income this way. It is said that this event happened at yaoi con, hence the interest of other people at the time, and the huge surge of requests for the yaoi paddles.
I originally made the first yaoi paddle, with woodburned letters and a high gloss acrylic finish for the owner of the company "hen da ne".
It was meant as a joke since he and I are friends and over 33% of his business relies on the sale of yaoi manga and doujinshi, and his business model includes yelling out catch phrases to passerbys in con dealer rooms (such as "geeeeet your red hot yaoi books right here!" and "hot boys in tight pants right here").
He liked the present so much, that he decided to mass produce them (to my dismay, without my final consent). And thus, has sold them ever since.
From http://adf-fuensalida.deviantart.com/journal/15376535
The post also said that the original yaoi paddle was invented in 2002/2003 by akicafe, and the rights of mass production have since been bought by hendane
Shortly after the start of the mass production, bans started to follow fast, due to the high number of "incidents" surrounding the paddles on cons. Several of these stories can be found online. All stating something along the lines of "I felt a intense pain running through my bottoms, as I turn around to see who did it, I see this small girl carrying a huge yaoi paddle melt into a group of people in cosplay with more paddles". Some of these cases even stated that the paddle broke/splintered, leading to their upgrade in 2005, and also the introduction of yuri/uke paddles.
In between 2004 and 2006, the paddles gained their massive media surge in response to the bans and police involvement. Following this media surge, even more bans occurred as a preventive measure on cons world wide.
TL;DR
They originate from a prank between a yaoi artist and his friend around 2002, following up the purchase of mass production rights in between 2002-2003.