Für das gezielte Austesten von Ideen würde ich dann eher kleine Prototypen mit einem "Jump'n Run" Maker a'la Game Maker erstellen. Da kann man dann nämlich einzelne Spielelemente und Steuerungskonzepte super austesten. Wenn's 3D sein soll vielleicht mit der Blender Game Engine oder Unity oder die einzelnen Mechaniken eben einfach in 2D auf generelle Designfehler testen...
Einfach mal mit einer Legofigur per Hand durch einen Parcours laufen oder eben eine Figur über ein gemaltes Level auf Papier gleiten lassen und dabei die Spielregeln einhalten, stelle ich mir aber auch sehr Ideen fördernd und sinnvoll vor. Obwohl man sich dabei vielleicht wie ein kleines spielendes Kind vorkommt, merkt man bestimmt schnell welche Moves cool kommen usw.
Ich selbst habe Paper Prototyping bisher nur für zwei Anwendungen genutzt (keine Spiele, ein Beispiel von meinen Kommilitonen und mir für ein Studienprojekt
http://www.youtube.com/watch?v=5TRCr5f6UdY). Das hat auf jeden Fall geholfen zu einer gemeinsamen Vision zu kommen und grobe GUI-Designfehler sowie falsche Vorstellungen im Vorhinein zu verhindern. So konnten wir außerdem auf eine allzu detaillierte Dokumentation, wie das ganze am Ende aussehen soll verzichten.
Bei Strategie-, Puzzle- und Denkspielen kann man damit ja nicht nur die Benutzerschnittstelle vorstellbar machen sondern sogar Gameplay und Balancing testen. Das ist für reine Actionspiele mit Papier natürlich nicht so möglich.
Was auch auf jeden Fall immer hilft sind Mockups, die im Grunde Screenshots des Spiels darstellen. Wenn man das ganze auf Papier macht und z.B. Lebensenergieanzeigen o.Ä. ausschneidet, bekommt man evt. leichter ein Gefühl von der GUI, als wenn man das ganze auf dem PC probiert. Viele schöne solcher (meist digital erstellten) Mockups findet man z.B. hier:
http://forums.tigsource.com/index.php?topic=7091 der Viewer
http://daid2.mine.nu/~daid/tigsource_pics/ für die reinen Bilder scheint leider gerade kaputt zu sein.