There are 2 different things that you're picking up on: catch phrases proper, versus copulas.
Both of these can be utilized in 1) making a character easy to remember, 2) setting the character apart in contrast to other characters in the same series (it is more common for only one character to sport a catch phrase in a series than for multiple characters to have one), and/or 3) epitomizing something about that character's qualities. Meaningless suffixes can likewise accomplish 1) and 2) but can't fulfill 3).
Naruto's "datte ba yo" is a catch phrase, since it is a stand-alone sentence that he can say whenever he likes. "Datte" means "because" or "but," or "da" is an informal copula (the formal version is "desu") + "-tte" means someone said it, so all together it could be translated to something like "'Cuz I say so." "Just 'cuz." "That's what I say." "Isn't it?" "Word." "Just, yeah." or "Yep."
Kenshin's "de gozaru" is not a catch phrase (see below). His catch phrase is "oro." The mangaka Nobuhiro Watsuki explained his catch phrase in an interview at AnimeExpo in 2002 (the English is from the interpreter's on-the-spot translation of his Japanese words):
Q: What is the origin of “Oro?"
A: I was surprised that it caught on like it did. Because it is just like saying “huh” or “uh” or “eh”. I am surprised that Kenshin used it so much, and that the fans caught on to it.
A good example of a catch phrase is Abe no Yasuaki's "Mondai nai" (meaning "It's not a problem") in Harukanaru Toki no Naka de, since it is neither a verb ending nor a suffix. It is simply a phrase he often uses, which encapsulates his stoic personality and that as an onmyouji he can handle pretty much anything.
Minami Mirei's catch phrase in PriPara, "Pop, Step, Get You!", is an interesting one since she coined it in order to craft an image of herself to project toward her fans, when in fact its buoyant perkiness does not match her real, secret personality.
Kenshin's "de gozaru" is a copula of "de aru" but it is not strictly associated with him. It is historical from the Edo period and became associated with historical series in general in the minds of Japanese people. Kenshin uses it in a period in which it was not common, highlighting his personality as humble and not following the fashion of the times.
Ika Musume's "degeso" is a creative adaption of a copula. It is a play-on-words (we could call it a pun or oyaji gag), but its intended meaning is to be simply understood as that of the copula "degesu" (meaning "to be").
Chichiri in Fushigi Yuugi ends sentences with "no da". "Da" is the most common and informal form of the copula, but inserting "no" makes it sound distinct without changing the meaning.
Mascots in the Pretty Cure franchise, characters in Di Gi Charat, and many other characters in anime, especially cute ones, tack a meaningless suffix onto their sentences. Rather than being a catch phrase proper, it is either 1) a repetition of part of their own name, 2) part of the name of something else in the series, or 3) a syllable or two that sound cute to the Japanese ear.
Minami Mirei in PriPara (mentioned above) appends the suffix "-puri!" onto many of her sentences in order to sound cutesy.