I don't think this question is answerable, at least not with a specific number. That's because a 6 letter word with lots of skinny letters (like "little") might take up less space than a 4-letter word with wide letters or lots of capitals (like "WIDE").
Even if you use a monspaced font, there is another difficulty. On possible answer is "as many characters as are needed to fully distinguish the text of one label from another." For example, if the user starts all of her labels with the 11-character string "Go to page ", then at least 12 characters (and possibly more) will be needed to keep two or more buttons from showing the exact same text. You would need to programmatically analyze the text that each user chooser for all of her labels in order to determine the minimum number of characters to show so that each label has unique text.
Based on the question ("I'm trying to decide on the maxwidth"), it sounds like you want to use the minimum number of characters needed in order to determine the maxwidth. But that seems backwards to me: Why are you setting a maxwidth to begin with? What is the fundamental reason?
If there is no fundamental reason to limit the width of the label, why not show each user all the text that they choose to enter? If there is no physical constrain, why should each label not grow as large as needed?
If there is some physical (or maybe aesthetic) constraint that limits the width of the label, then THAT should be the starting point. Maybe you don't want any label to exceed one-third of the screen width, or for the width to be more than 5 times the label height. That's fine. But decide the maxwidth first. Once you know the maxwidth, THEN you can determine how many characters you can fit into that space.
If using a monospaced font, you can use trial and error to determine the max number of characters that fit.
If using a proportional font, I don't think you can come up with a number of characters: Even once you know the maxwidth you can afford, the number of characters simply cannot be predicted in advance since there is so much variability in the text entered by the user and the variable width of each character. Any kind of estimation or averaging approach will fail in edge cases.