在欧洲中世纪，特指西罗马帝国灭亡-文艺复兴期间，天主教/东正教/新教地区，如何成为一个king，大致需要多大面积的领地，需要多少领主(公爵/伯爵)效忠，是否需要教会认证许可？找片无主之地，招募一批流民，建个城堡，自己封王是否可以？
在中世纪的欧洲成为国王有很多方法。根据题主描述，这里的国王，是指被欧洲郡主和教皇广泛承认的国王，属于公侯伯子男这个系统。任何一个有栖息地的民族的领导人都会用“王”这个称号，但并非属于本题里所描述的“国王”
首先必须搞清楚的是，欧洲是先有王这个称呼，后有封分体系。西罗马帝国式微后，众多日耳曼蛮族进入高卢定居。他们的首领大多是由部落联盟会议选举出来的军事领袖，在原始德语中被称为kuningaz，是英语里king的词源。欧洲各蛮族国家基督教化后，国王这个词的含义才从部落首领变成了封分阶层中的一级。
第一种:当然是继承，你爹你爷爷你哥哥你老婆，各种勾心斗角后宫大戏我就不说了第二种:皈依天主教的异族首领，由梵蒂冈天主教教皇册封为国王。
这个情况比较好的例子是第一个匈牙利国王伊斯特凡一世。他于公元997年登基时被叫做“GrandprinceofHungarians”(匈牙利人的亲王)，这里的prince并非指王子，而是指比国王低一等级的亲王。这个职位是马扎尔人(匈牙利人)部落联盟的首领，并不属于欧洲的体系。根据匈牙利的传说，公元1000年的圣诞节，教皇把象征法统的王冠和权杖送到了这个匈牙利首领的手中。凭借这两件圣器，部落联盟酋长加冕成为匈牙利人的国王，伊斯特凡一世;匈牙利也自此升格成为王国。
最初的王冠和权杖至今任然保存在匈牙利国会大楼内，象征着国家的权利。1945年苏军占领前夕，匈牙利人曾经秘密把这两件圣物交给美军保管，美国最终也于七十年代将其交还。
保加利亚是一个很有趣的特例，在九世纪末鲍里斯一世皈依君士坦丁堡东正教之时，保加利亚自称帝国，领导人称可汗。君士坦丁堡牧首给予鲍里斯一世大公的头衔。所以他是“保加利亚帝国的大公”。后来的西蒙一世又自称沙皇。斯拉夫语里沙皇是皇帝的意思，和罗马皇帝平起平坐。但欧洲国家普遍把沙皇当做国王。
克洛维一世是法兰克王国第一个受洗礼的国王，同时也被认为是现代法兰西名族的根基。他于公元486年击败残存在高卢的西罗马势力后，被广泛地认做全法兰克人的王。
法语中的“roi”就是王的意思，而其后一直到1830年的路易菲利普一世，法王都被称为“roi”。最开始，克洛维一世的祖父异教徒梅罗纹加称王的时候，显然没有受到教皇认同，但随着克洛维一世皈依天主教后，法兰克王国和梵蒂冈越走越近，教皇也就自然地承认了法兰克郡主为国王。
第三种情况就是题主所问的，能不能带一批人去一片荒凉的地方称帝。首先，想要自称帝的话，有一亩三分地就足够了，参考部落时期的匈牙利;然后只要你艰苦奋斗，把自己的地盘扩张到教会无法忽视的地步，他们就会承认你为国王。
但想要从一开始就被承认，就只能稳扎稳打从低的爵位开始做起，然后顺着公侯伯子男的顺序一路往上爬。通常是一个拥有帝国头衔的国家把一个公国升格为王国符合这种模式的有普鲁士王国。普鲁士王国的前身是条顿骑士团属地，领导人是骑士团团长，名义上属于梵蒂冈的管辖范围。由于和波兰的数次冲突皆以失败告终(坦能堡会战)，条顿骑士团和其属地也需要效忠波兰王国。
16世纪初，受马丁路德的新教运动影响，条顿骑士团团长勃兰登堡的阿尔布雷希特宣布切断与梵蒂冈的联系，骑士团属地升格成为普鲁士公国，他也成为第一任普鲁士大公。波兰王国认可普鲁士大公为其分封的附庸。此后勃兰登堡选帝侯国的霍亨佐伦王朝取得了普鲁士公国大公的继承权，两国遂成为共主联邦，脱离了波兰的控制。
普鲁士王国诞生于1701年的西班牙王位继承战争。普鲁士公国通过和哈布斯堡王朝把持的神圣罗马帝国结盟，促使其升格普鲁士公国为普鲁士王国。弗里德里希一世是首位普鲁士国王。
第四种是由本国国会选择。适用于君主立宪的国家。例子不用我多说了吧，1688年的光荣革命，英格兰上议院的大佬挑了荷兰来的的威廉三世来当英格兰国王。原因是威廉三世娶了前国王的女儿，同时又是新教徒。后来威廉三世绝嗣，于是国会又选了汉诺威王朝的乔治一世来当国王。此君英语说的估计都没蛤蛤好，对国事也是毫不在意，英格兰国王自此开始向现代君主立宪发展。
第五种，就是和以前的国家套关系找立国的法统。
俄罗斯帝国的源头是丹尼尔亚历山德诺维奇创立的莫斯科公国。莫斯科公国公爵的称号是他父亲诺夫哥罗德大公涅夫斯基给他的，而涅夫斯基的这个爵位，好吧，是蒙古人给他封的。他的后人伊凡四世(伊凡雷帝)于1547年决定把莫斯科公国升格为俄罗斯沙皇国(Tsardom)，因为他爸爸娶了拜占庭的最后一位公主(虽然伊凡四世本人不是这位拜占庭公主生的)。
既然继承了罗马帝国的衣钵，俄罗斯的皇室们就可以爱怎么搞怎么搞了，不需要别人承认，因为别人都不如自己的法统来的伟光正啊。这个沙皇国到底是帝国还是王国也是搞不清楚，从英语语法上来看沙皇国“tsardom”看起来很像王国“kingdom”，但斯拉夫人认为tsar这个称呼和罗马皇帝平级。。于是这个时候的俄罗斯其实是介于王国和帝国之间的一种。。皇帝国╮(╯▽╰)╭。不过其实既然是自己封自己，随便怎么解释也没问啦。后来彼得大帝终于把沙皇国改成了帝国。
到了十八十九世纪，教会在政治上的发言越来越少。原先对国号的苛刻规矩也没多少人在意了。拿破仑称帝后，法兰西变成了一个帝国。1801年神圣罗马帝国解体后，奥地利国王弗朗茨二世赌气似的把自己国家升格成了奥地利帝国，自任皇帝。俾斯麦统一德国后也把威廉一世推到了德意志帝国的宝座。原本只能由罗马人享有的帝国和皇帝等称号在工业革命后的欧洲层出不穷。
纵观历史，称不称王，称不称帝其实并不重要，重要的是一个国家独立自主的内政外交和综合国力。王国和国王只是一个名分，多半是教皇或帝国拉拢别国时的政治筹码。英格兰从来没有称帝国，但她曾经的繁荣超过了地球上曾经出现过的任何帝国。
(至于人口限制，我倒是知道美国的NorthwestOrdinance规定一个地区要公投是否以州的名义加入联邦需要一万六千人的人世界口。王国什么的，名义上有王的血统就可以了吧。)
