Here is my Python 3.x code. Comments welcome:

import numpy as np
from itertools import chain, product


def navigate(flrsmap):
    npmap = np.array([[list(row) for row in flr.split('\n')]
                      for flr in flrsmap.split('\n\n')])

    def navrecur(poses):
        curpos = poses[-1]
        endposes = None
        moves = product([1, 2], [-1, 1])
        if npmap[curpos] == 'U':
            moves = chain(moves, [(0, -1)])
        elif npmap[curpos] == 'D':
            moves = chain(moves, [(0, 1)])
        for axis, step in moves:
            newpos = list(curpos)
            newpos[axis] += step
            newpos = tuple(newpos)

            if newpos in poses:
                continue
            if npmap[newpos] == '#':
                continue
            if npmap[newpos] == 'G':
                return poses

            resposes = navrecur(poses+[newpos])
            if resposes is None:
                continue
            if endposes and len(resposes) > len(endposes):
                continue
            endposes = resposes
        return endposes

    curpos = tuple(x[0] for x in (npmap == 'S').nonzero())
    poses = navrecur([curpos])
    for pos in poses:
        if npmap[pos][0] not in 'SUDG':
            npmap[pos] = '*'

    return '\n\n'.join('\n'.join(''.join(row) for row in flr) 
                       for flr in npmap)

flrsmap = """##########
#S###    #
#   # ####
### # #D##
#   # # ##
#D# # # ##
###     ##
### ### ##
###     ##
##########

##########
#   #   D#
#     ####
###   # ##
#U#   # ##
# #    D##
##########
#       ##
#D# # # ##
##########

##########
#        #
# ########
# #U     #
# #      #
# ####   #
#    #####
#### ##U##
# D#    ##
##########

##########
#        #
# ###### #
# #    # #
# # ## # #
# #  #   #
# ## # # #
# ##   # #
#  #####G#
##########"""

print(navigate(flrsmap))

And my results:

##########
#S###    #
#***# ####
###*# #D##
#  *# #*##
#D#*# #*##
###*****##
### ### ##
###     ##
##########

##########
#   #***D#
#    *####
###  *#*##
#U#  *#*##
# #  **D##
##########
#*******##
#D# # # ##
##########

##########
#********#
#*########
#*#U     #
#*#      #
#*####   #
#****#####
####*##U##
#*D#****##
##########

##########
#********#
#*######*#
#*#    #*#
#*# ## #*#
#*#  #  *#
#*## # #*#
#*##   #*#
#**#####G#
##########