Metagame Paradox: what is wrong with this explanation?
The flaw is that your definition of "game" is deficient and does not correspond to our intuition.  We also need a restriction on the number of moves that are possible at any position in the game.   It doesn't really have anything to do about computability, so much as about the notion of what it means for a game to be finite.



Usually we define a game as something where at each step there are only finitely many moves that can be played, and where the game is guaranteed to end after finitely many moves (there is no infinite sequence of moves in the game).  You forgot to specify the "at each position, there are only finitely many moves possible from that position" in your definition of a game.

If you add that to the definition, then you'll find that the metagame does not meet the definition: the metagame is not a game.  In particular, there are infinitely many possible games, so at the beginning of your metagame, there are infinitely many possible moves -- thus the metagame does not qualify as a game.  There is no paradox.



You could have an alternative definition of a game where you say that at each step the number of moves is either finite or countably infinite.  This is a bit different from what our intuition would suggest, but let's explore the consequences of defining a game this way.

In particular, the set of all games would now be uncountably infinite. 

As a result, the metagame is still not a game: at the beginning of your metagame, there are uncountably infinitely many possible moves -- so does not qualify as a game.

In particular, "pick a game" is not meaningful: Player 1 has to select a game and describe it to Player 2, but there are uncountably infinitely many possible games, so Player 1 cannot describe his choice in any finite amount of time.  In particular, you cannot specify a game with a finite string (more precisely: no matter what candidate encoding of games you come up with, there will exist some games that cannot be specified by any finite string).  The description of the game is an infinite-length string.

If you like to think of it intuitively: in this case it wouldn't really be fair to think of the metagame as "finite" (even though it only lasts for a finite number of moves, if the first move takes infinitely long to complete, the metagame cannot be considered finite).

In any case, if you define a game this way, there is still no paradox.

(Why is the set of games uncountably infinite, if this is how we defined a game?  Well, I'll show an injective map $f$ that maps from a real number $x \in [0,1]$ to a game $G_x$.  In the first move of $G_x$, player 1 chooses a natural number $n \in \mathbb{N}$.  After that, there are $n$ more moves, then the game ends.  At the $i+1$th move (for $1 \le i \le n$), there are $x_i$ different moves available to the player whose turn it is to move, where $x_i$ denotes the $i$th digit after the decimal point in the decimal expansion of $x$.  Notice that $G_x$ qualifies as a game: there are two players, the players alternate, there are finitely or countably infinitely many moves at each possible position of the game, and the game is guaranteed to end after finitely many steps -- there is no infinite sequence of valid moves.  But the set $[0,1]$ of real numbers is uncountably infinite, and we have an injective map from an uncountably infinite set to a subset of the set of games.  Therefore, the set of all games is uncountably infinite, under this definition.)



Finally, the last alternative would be to define "game" so there is no restriction on the number of possible moves at each position.

However, this definition of a "game" would no longer correspond to our usual intuition for what a game should involve.  In particular, it may not be possible for a player to describe his/her move to the other player in any finite amount of time (since he/she may be choosing from among uncountably infinitely many possibilities).  That just ain't right.  In particular, such a process can't reasonably be considered finite: it would not complete in any finite amount of time.



Intuitively, why does it make sense that our definition of game ought to restrict the number of possible moves at each position to be finite, or at most countably infinite?  Because we need the player to be able to select a move and describe it to the other player.  If there is no finite encoding of the set of possible moves (at a given position), then the player whose turn it is to move has no way to describe the move he chose to his opponent.  If there is a finite encoding of the set of possible moves (at each possible position), then the number of possible moves must always be finite or countably infinite, by the definition of countability.