There are tools around but probably better to teach yourself to do it in Excel, here's a rough idea how (assuming they are all in the NY 100km square and your grid refs are in column A, starting from A1)
In the first free cell of column B type the following =LEN(A1)
Then hover your cursor over the bottom right corner of the cell and drag the little + sign that appears downwards until you reach the bottom row of the grid references. That will populate the whole of column B with numbers representing the length of each grid ref.
Now sort the spreadsheet by column B to get all the grid refs of the same length appearing together and handle each block separately.
For the six figure grid refs 8 characters long as in your example (assuming these start at cell A1)
In the first cell of column C type this = "3" & MID(A1, 3, 3) & "00"
In the first cell of column D type this = "5" & Right(A1, 3) & "00"
Select both the cells you have just typed in and drag the + sign down to the end of the six figure refs.
When you have got the hang of that do eight figures by changing the second 3 in the C column expression to a four and reducing the number of zeros at the end to just one. For the D column expression change the 3 to a 4 and reduce the zeros to one.
That should be all the information you need and it should take less time than I have to write this.
Who needs a tool?
By the way, before opening in GIS you should select and edit/copy the C & D columns, then edit/Paste special them back onto the same location as values (overwriting the formulas you typed) otherwise they may come out as something unexpected in your GIS
Rob Large
Wildlife Sites Officer
Wiltshire & Swindon Biological Records Centre