Is it correct to use 首都 for capital of province?
No, you should use 省会 (provincial capital) instead, i.e. 哈尔滨是黑龙江的省会. You could also use 省城 (in a little old-style), or 首府 (especially for 自治区(autonomous region)).

首都 is only used for the capital of a country, e.g.北京是中国的首都.