For all the animals described in "Everyday Life on a Hypergeometric Earth", Patrick preferred paired limbs due to developmental simplicity--which, e.g., rules out 3-winged birds.
However, based on the examples of starfish, whales, and plants, I think there are reasonable ways for 4D animals to evolve groups of 3 limbs--but 4D starfish would not be among the animals that actually would!
Starfish start out bilaterally symmetric, and then a radially-symmetric adult develops attached to one end of the larva, which is later resorbed by the mature adult body. When you start from hundreds or thousands of cells, binary division is not longer a major influence of symmetry--and while standardly-3-way symmetric animals are all extinct, you can see 3-way symmetry developing in the same way in jellyfish (moon jellies are usually 4-way symmetric, but 3-, 5-, and 6-lobe individuals all exist) and various plants (like 3-leaf clovers). So, there's one option for getting animals with 3-way planar symmetry in their limb girdles--start out with a limbless larval/embryonic form, which then grows limbs secondarily.
Whales and snakes provide examples of another possible path--limb loss. Suppose an animal begins with tetrahedral or 4-way symmetric limb girdles. Just like whales lost one whole limb girdle (because the back legs were not useful in water), and snakes lost all of their limbs, such a creature could evolve to turn off development of one limb out of four, resorb it, and re-arrange the remaining three limbs for planar symmetry. This requires initial breakage of symmetry to select a limb to lose, but 3D animals aren't basically never internally symmetric anyway, and creatures like crabs can have very noticeable external symmetry-braking as well (e.g., to develop one large crusher claw and a smaller claw), so that's not really a problem for an embryo or fetus to do. So, three-winged birds should be entirely possible.
4D starfish, however, would ironically not have odd-numbered planar symmetry. A 3D starfish is 3D-flat, with arms spanning the plane--and because their limbs are arranged in a plane, they can have any number of evenly-space arms (and some have quite a lot more than 5), corresponding to regular polygons. But a 4D-flat starfish would crawl along a 3D seafloor with arms spanning the hyperplane--which means the possible arrangements of arms are restricted by the existence of regular polyhedra. Thus, a 4D starfish would have to have 4, 6, 8, 12, or 20 arms--but each arm could, internally, have trilateral or pentalateral symmetry in the arrangement of water channels and tube feet.
Incidentally, I have been developing my own 4D story world for quite some time--it's too bad I didn't discover this forum 12 years ago!--and I also went with 4-armed human-analogs, rather than the more parsimonious 3, but not for developmental reasons--rather, because I find it a lot easier to think about and refer to a person's left, right, ana, and kata arms/hands, rather than figuring out how to refer to and describe each of 3 limbs spanning the left-ana plane in non-orthogonal axes.