The Leap Motion side of this shouldn't be too difficult assuming that you know a bit about programming and geometry.
Physical setup
You need to construct something that will keep the Leap Motion device and the paper board from moving in relationship to each other. Also, the touchable parts of the board must all be within the Leap's field of view (which is an inverted pyramid, not a rectangle).
Software
You'll need a calibration step where you define the shapes that viewers can interact with. You can do the same thing as in the video you cited, touch a point on the board and click a key to mark a point. You will need to save these shapes for use later in your program and give them a name or id. (And if the device or board shift in relationship to each other, you'll have to redo this step.)
The Leap Motion software produces "frames" of tracking data, which you can get from the Controller object. At regular intervals, you would get a frame of data and look at the finger tip positions. If any of these tip positions are close enough to your defined shapes to be considered touching, then you trigger the action for that shape.
The Leap SDK supports C++, C#, Objective-C, Python, Java, and JavaScript. There's also an ActionScript library available.