Use the tf.exe tool from the Visual studio commandline – it can handle wildcards:
tf.exe move <olditem> <newitem>
Example:
tf.exe move "$/My Project/V*" "$/My Project/Archive"
[EDIT] As noted in the comments: move is an alias for rename. Both commands move history.