As has been mentioned in the comments, this could easily be explained as an early indicator of Tuvok's neurodegenerative disease. One could also blame side effects of the memory virus from "Flashback." There is also the fact that Tuvok's studies of various Alpha Quadrant martial arts, archery, and Starfleet combat experience give him different tendencies than the more science and diplomacy focused Vulcans we've seen throughout the show.
Regardless, the most likely cause is that Tim Russ fidgets. Though the other two actors playing Tuvok over the years have had small parts, neither LeRoy D. Brazile nor Demetris Lawson showed a single sign of fidgeting.