Method can be made static, but should it?

Static methods versus Instance methods
Static and instance members of the C# Language Specification explains the difference. Generally, static methods can provide a very small performance enhancement over instance methods, but only in somewhat extreme situations (see this answer for some more details on that).

Rule CA1822 in FxCop or Code Analysis states:

"After [marking members as static], the compiler will emit non-virtual call sites to these members which will prevent a check at runtime for each call that ensures the current object pointer is non-null. This can result in a measurable performance gain for performance-sensitive code. In some cases, the failure to access the current object instance represents a correctness issue."

Utility Class
You shouldn't move them to a utility class unless it makes sense in your design. If the static method relates to a particular type, like a ToRadians(double degrees) method relates to a class representing angles, it makes sense for that method to exist as a static member of that type (note, this is a convoluted example for the purposes of demonstration).

Marking a method as static within a class makes it obvious that it doesn't use any instance members, which can be helpful to know when skimming through the code.

You don't necessarily have to move it to another class unless it's meant to be shared by another class that's just as closely associated, concept-wise.

Performance, namespace pollution etc are all secondary in my view. Ask yourself what is logical. Is the method logically operating on an instance of the type, or is it related to the type itself? If it's the latter, make it a static method. Only move it into a utility class if it's related to a type which isn't under your control.

Sometimes there are methods which logically act on an instance but don't happen to use any of the instance's state yet. For instance, if you were building a file system and you'd got the concept of a directory, but you hadn't implemented it yet, you could write a property returning the kind of the file system object, and it would always be just "file" - but it's logically related to the instance, and so should be an instance method. This is also important if you want to make the method virtual - your particular implementation may need no state, but derived classes might. (For instance, asking a collection whether or not it's read-only - you may not have implemented a read-only form of that collection yet, but it's clearly a property of the collection itself, not the type.)