My solution would involve meshgrid and some fancy arrayfun action (though you could easily replace arrayfun with a for loop)
%Some matrix
data = rand(5)
%Get a matrix of row numbers
rows = 1:size(data,1);
cols = 1:size(data,2);
[rowNums,colNums] = meshgrid(rows,cols);
%Combine it with original data
combineFunction = @(rownum,valnum) [num2str(rownum) ':' num2str(valnum)];
res = arrayfun(combineFunction, rowNums, data, 'UniformOutput', false)
Note you could then quite easily use something like xlswrite to export the res matrix.
