I need a pet with a consitution of over 60 to start building the lv 2 inventory/warehouse and lv 2 stable, but my pets' characterisitcs are not increasing.  I explored for a while and leveled some of them up and made sure of their diet was 5 stars for consitution, but none of their stats changed.  Do I need to wait a while for it to update?

The five stars doesnt give a guarentee to have it increase with each level, but it gives you the best chances for it to. You got some bad luck maybe, or they just need more levels to actually get an increase. If even with many many levels none of the characteristics increase by even 1 then theres probably something wrong.