Convergence guarantees for basic RL algorithms like policy gradient / actor-critic methods make no assumptions about the dynamics of the MDP. So, theoretically, you don't need to change much.
Practically, when the number of possible trajectories from any given state is so high, the return from each state will have high variance. This means you'll have to collect much more experience for your estimates of expected return to converge to their true values. Intuitively, an environment with high uncertainty requires the agent to do more knowledge-gathering to behave optimally.
My real advice to you depends on what exactly you're trying to do. If you want to have the kind of agent that could learn to behave well in an extremely random environment, then all you need to worry about is giving it enough experience to learn from.
(Your agent should also take a little longer before deciding it's "confident" in its evaluation of different states. That is, don't behave greedily before you're sure your estimates are accurate. Explore adequately. This advice is only relevant if your MDP dynamics aren't actually completely uniform.)
If, however, you want to train an RL agent specifically to solve a problem formulated as an MDP with uniformly random dynamics, then I would tell you to not waste your time. We know before spending the computation that all policies would be equally good/bad in this setting. Since actions are irrelevant to the environment, it would be inefficient to deploy an RL agent that will only learn that which action it takes doesn't matter.
As noted in the comments, the last paragraph is only true when reward from each state-action pair $(s,a)$ is also uniformly random. If it is not, just being aware of the high variance and giving your agent a lot of experience should do the trick.