Cleaning address line data sent to couriers API
First I'd think about names. Isn't Clean() enough for a method inside a class named StringCleaner? Do you need to repeat String?

Still in the prototype you should consider that you're iterating char but replacement is a string. It might be (or not) something to consider, it depends on your requirements.

More about char and string: you're iterating char (which is an UTF-16 code unit). UTF-16 is not fixed size then you're breaking for code points which are not encoded as a single code unit. More about Unicode: not every character is a single code point: you're breaking for surrogates. String might be (or not) normalized, do you need to take care about  it? One grapheme may be represented using two or more code points: think about, for example, ộ Vietnamese character. You may read How can I perform a Unicode aware character by character comparison?

For now let's assume that to iterate char is perfectly fine. If not then read an almost ready to use example in Split a string into chunks of the same length.

In .NET strings are immutable then reading String.Length in a loop is perfectly fine and compiler is capable to optimize it. You already know the maximum length of the string then you may preallocate the StringBuilder buffer to the maximum capacity:

var newString = new StringBuilder(stringToClean.Length);


foreach will help to make code shorter and easier to follow:

foreach (var c in stringToClean)
{
    if (ValidCharacters.Contains(c))
    {
        newString.Append(c);
    }
    else
    {
        newString.Append(replacement);
    }
}


If replacement can be a char it's even easier:

foreach (var c in stringToClean)
    newString.Append(ValidCharacters.Contains(c) ? c : replacement);


You may want to see a LINQ version (in case you find it more readable):

new String(stringToClean.Select(c =&gt; ValidCharacters.Contains(c) ? c : replacement));


Performance

In general you should be careful with parameters with a default value, in this case also because of performance. If you add an overload for the common case then you can write:

public static string CleanString(string stringToClean)
    =&gt;  new String(stringToClean.Where(ValidCharacters.Contains(c)));


Searching each character inside the array is something terribly slow. First approach: HashSet&lt;char&gt;. Build the list and search inside the hashed collection. It's WAY faster.

We're talking about true/false values and all valid characters are inside the 7 bit ASCII range...if performance really matters you may use a BitVector. Unfortunately default implementation throws ArgumentOutOfRangeException if you ask for a value outside the assigned range; if you do not want to create a vector of 2^16/8 bytes then you may write your own implementation (see for example Count items existing in 2 Lists for a quick and dirty comparison).