How to replace spaces with dashes when redirecting users through Rules?
Sometimes the solution to a problem, is to prevent the problem from happening.

So therefor I suggest you just do not allow spaces in your user names. To do so, use the Rules module (which you already have), and implement a rule that looks something like so:

{ "rules_disallow_spaces_in_user_names" : {
    "LABEL" : "Disallow spaces in user names",
    "PLUGIN" : "reaction rule",
    "ACTIVE" : false,
    "OWNER" : "rules",
    "REQUIRES" : [ "rules" ],
    "ON" : { "user_presave" : [] },
    "IF" : [
      { "text_matches" : {
          "text" : [ "account:name" ],
          "match" : "\\b \\b",
          "operation" : "regex"
        }
      }
    ],
    "DO" : [
      { "drupal_message" : {
          "message" : "User names are not allowed to contains spaces, please correct",
          "type" : "error"
        }
      }
    ]
  }
}


Some more details about this rule (which you should be able to import in your own site using the Rules UI):


Rules Event: "Before saving a user account".
Rules Condition: use a regex to check of the user name contains a space (adapt the regex if needed).
Rules Action: set an appropriate error message (adapt if needed).


The additional advantage of this approach is also that you don't need the PHP filter for it to work (as suggested in one of the comments).