I think the assumption there is that the alien race is smart enough and dexterous enough to create machines. Wether they use tentacles, fingers, snouts or talons, it makes sense that such a species develops board games at a moment
While not exactly movie and not specifically sea creatures/birds, there are plenty of anime series and visual novels with intelligent non-humanoid alien species. Parasite from Parasyte, some forms of BETA from Muv-luv, aliens from Stellvia, (NSFW to Google) Saya from Saya no Uta (real form). Dragons are also often portrayed as intelligent race originating from space (e.g. Final Fantasy XIV & Kumo Desu ga, Nani ka?). Many of these usually have a way to appear as humanoid to make conversing with mankind easier though (and likely to make it easier for readers/watchers to relate).
It's worth pointing out that Go is a purely mathematical game. You don't need a board at all to play it, especially not if your memory is good enough. Chess Grandmasters don't need boards to play Chess, for example; they can simply say the moves to each other and both will have the same image of the board in their mind.
So you could have intelligent aliens playing Go entirely verbally. Considering how many alien species there are likely to be, perhaps this is almost a certainty?
Is it common to be able to play Go without a board? That seems to require storing 361 bits in your head. I guess it’s much sparser than that for most of the game and has more structure than just 361 random bits, but that still sounds hard.
Here’s a (strong?) amateur who claims to be the only person who can play this way [1].
But yes, there are even some people that can play Go in their head. You're wrong about the amount of information though; each piece on the board has 3 potential states, not just two. Though you can chunk the board pretty effectively and it becomes more about memorizing larger patterns than the state of every single spot on the board. Plus, the board never fills up, so you only need to remember the spaces with pieces in them, not every space.
Also, 400 bits of information is about two sentences.
We might one day have octopuses play Chess with us. But there may be other alien games we'd learn from them as well. Or not.
The little-known Star Trek IV: The Voyage Home centers its plot around the idea that Earth whales are themselves aliens. A crisis occurs when a whale probe comes to check on the Earth whales.
I think the body shape part is relevant here because it determines what kinds of games are possible or practical. A species of intelligent octopuses might play games involving changing their pigment (in wavelengths we can't even see!) or manipulating eight things at once. Bird games might involve flying competitions etc.
Edit: I guess the important part here in a species inventing Go, is having a body that can make a board game (or similar representation). Hands are pretty good for crafting tables and moving small pieces around. Beaks and snouts less so. (I'd put my money with the octopus.)