Update datatype of primary key without deleting the table
You cannot change datatypes of Key fields (Primary or Foreign). You can't even change a datatype if the field is used in an index. So...

If there is no data in these tables (obviously much easier):


Drop Foreign Key on [Addresses] that references [State]
Drop Primary Key on [State]
ALTER TABLE [State] DROP COLUMN [StateID];
ALTER TABLE [State] ADD [StateID] INT IDENTITY(1, 1) NOT NULL;
Recreate Primary Key on [State]
ALTER TABLE [Addresses] ALTER COLUMN [StateID] INT NOT NULL;
Recreate Foreign Key on [Addresses] that references [State]


If there is data in these tables (and you have a maintenance window):


ALTER TABLE [State] ADD [StateID2] INT IDENTITY(1, 1) NOT NULL;
ALTER TABLE [Addresses] ADD [StateID2] INT NOT NULL CONSTRAINT [DF_Addresses_StateID2] DEFAULT (0);
Update the [Addresses] table to match the new IDs in the [State] table

UPDATE addr
SET    addr.StateID2 = st.StateID2
FROM   Addresses addr
INNER JOIN [State] st
        ON st.StateID = addr.StateID

Drop Foreign Key on [Addresses] that references [State]
Drop Primary Key on [State]
sp_rename [State].[StateID] -> [StateIDold]
sp_rename [State].[StateID2] -> [StateID]
Recreate Primary Key on [State].[StateID]
ALTER TABLE [Addresses] DROP CONSTRAINT [DF_Addresses_StateID2];
sp_rename [Addresses].[StateID] -> [StateIDold]
sp_rename [Addresses].[StateID2] -> [StateID]
Recreate Foreign Key on [Addresses].[StateID] that references [State].[StateID]
Update Stored Procedure(s) or whatever processes/code insert (and possibly update if the StateID field can change) into the [Addresses] table
After you are sure that all data is there and matches, then you can drop the [StateIDold] field in both the [State] and [Address] tables.


If there is data in these tables (and you do not have a maintenance window):

If there is no maintenance window then you have to not only deal with contention on the table (and adding / removing fields requires a SCHEMA lock), but you also need to update the process that adds data to the [Addresses]


Build copies of both tables [Addresses2] and [State2] with the desired structure (but no FK)
Copy the data over to the new tables
make sure no data in [Addresses] can change (this is very temporary)
rename current tables (e.g. [Addresses] -> [AddressesOld])
rename new tables (e.g. [Addresses2] -> [Addresses])
Add FK
Be sure to update code that inserts into Addresses
Allow changes in [Addresses] again


For a more detailed explanation of this "no maintenance window" approach, please see the article I wrote about it on SQL Server Central (free registration required): Restructure 100 Million Row (or more) Tables in Seconds. SRSLY!