We investigate the spatiotemporal dynamics of a lattice of coupled chaotic maps whose coupling connections are dynamically rewired to random sites with probability p, namely at any instance of time, with probability p a regular link is switched to a random one. In a range of weak coupling, where spatiotemporal chaos exists for regular lattices (i.e. for p = 0), we find that p > 0 yields synchronized periodic orbits. Further we observe that this regularity occurs over a window of p values, beyond which the basin of attraction of the synchronized cycle shrinks to zero. Thus we have evidence of an optimal range of randomness in coupling connections, where spatiotemporal regularity is efficiently obtained. This is in contrast to the commonly observed monotonic increase of synchronization with increasing p, as seen for instance, in the strong coupling regime of the very same system.