Doing a SELECT * with no WHERE-clause will always do a scan, either a Table Scan in the case of a heap, or a Clustered Index Scan in the case of a table with a clustered index.
The difference in time in your first experiment was likely due to fragmentation and the presence of lots of forwarding pointers. Before you added the PK you had a heap, i.e. a table with no clustered index. When you added a PK a clustered index was also added implicitly to support the constraint and so the heap became a clustered table and was defragmented in the process, which improved performance of the scan of all the data.
In general it is considered good practice to start with the idea that all tables in SQL Server that might be accepting inserts, updates and deletes on a regular basis should have a clustered index. A primary key is also considered a good thing to have. The PK and the clustered index do not have to be on the same set of columns but it you create a PK on a table with no clustered index and you do not specify that the PK should be nonclustered SQL Server will use the PK key columns and generate the supporting index as clustered using those some key columns.
There are no special teachers of virtue, because virtue is taught by the whole community. --Plato