Automator: Decode Decode64 selection and display output in a new TextEdit window
I know the question is about TextEdit, but for anyone who would rather do this in BBEdit, you can create a TextFilter to process the selected text.
#!/usr/bin/python

import sys
  
def decode64(myString):
    return myString.decode('base64')

input = sys.stdin.read()
print decode64(input)

If you want to use python3, it's even easier:
#!/usr/local/bin/python3

import sys, base64

input = sys.stdin.read()
print base64.b64decode(input)

Save this to: ~/Library/Application Support/BBEdit/Text Filters, then you can access it from the Text Filters menu.