With only using PairExists, yes, I think you would probably have to consider all valid responses and all invalid.
Depending on the needs of the business, you might be able to summarize each level into "valid" or "invalid", using a multiple PairExists, such as
Menu1Valid=PairExists("Menu1", "1")|PairExists("Menu1", "2")
Menu1Invalid=~(PairExists("Menu1", "1")|PairExists("Menu1", "2"))
This might be easier than trying to specify all the individual possibilities, such as
Menu1_1=PairExists("Menu1", "1")
Menu1_2=PairExists("Menu1", "2")
Menu1_Invalid=~(PairExists("Menu1", "1")|PairExists("Menu1", "2"))
etc...
Depending on your skillset (or the skillset of your team), you might also be able to write this information into a custom table on your database server, then report from there. As part of postcall wrapup, you might be able to create a large KV string from your attached data, then pass it into a stored proc for insertion into the custom table, with the user information and call date/time attached. Then you can use intrinsic SQL functions (such as count() in Sybase or MSSQL) to count the number of calls that occurred within a specific period. (Of course, this gets into the whole issue about the Genesys Brio license only being licensed for your datamart...)
Of course, another option is Call Concentrator. Based on what I was able to gather from the documentation, this records all the attached data (or the UAD you select) for each call. You then use a thirdparty reporting tool (Brio, Crystal Reports, etc) to extract and report on the data.