In my current game I was around level 22, around 160 days, I owned Uxkhal, Halmar and Dhirim. I rebel when I was refused Dhirim.
I do not remember what were my renown (found 619 on a screenshot) and right to rule (maybe 10/15).
Basically, you want to have at least 2 (preferably 3) towns or castles in a nearby group, and the army size to take on any king's army or a group of smaller armies without major losses. That will allow you to assign fiefs to either a couple of your noble Companions or to friendly Lords who you convince to join you, and a reasonable ability to defend that region against the inevitable attempts to take it from you. You also want to be on very good terms with at least one lord of the faction you're quitting, so you can offer a peace settlement quickly at a reasonable price, rather than fighting the entire faction gathered against you.
Currently, I'm up to around 150 days into my present campaign, and have two castles some distance apart. There is no way that I can be in two places to defend both. Taking a town near one or the other is a practical necessity before I dare proclaim my own kingdom, but not something I can do while I'm in a faction that's not at war with either of the kingdoms I need to take one from. I'm also a bit low on renown, still in the 400-500 range, and can't quite field 100 troops. There is no single criterion to judge when it's "safe" to declare your own kingdom, it depends on a large number of conditions and factors which will vary in importance from one campaign to the next. The game requires both skill and some luck to pull all of the pieces into place quickly, but fortunately I'm not in a screaming rush to force the issue. Another two or three months should be sufficient to bring renown and force size up to par, but I'm still dependent on my sworn liege to declare the "right" war to set up the proper conditions. Meanwhile, I'm just bashing bandits and Swadians for fun and profit.
Dhirim is a sore subject at the moment. I besieged the town, easily drove off one attacker during the wait to build a siege tower, and then my faction unexpectedly accepted peace with the owner of the town. Roughly two months later, my faction declared a new war against them, and the faction marshal immediately laid siege to the town and took it easily. It now belongs to another member of my current faction. I feel like I was robbed.