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
Wildlife Sites Officer
Wiltshire & Swindon Biological Records Centre